1424 . 小方塊的樹學實驗
TopCoder
Tags
Description
小方塊作為世界知名的樹學家，每天最喜歡做的事情就是研究樹學。這天，小方塊開發出了一種全新的樹學技巧，可以把一棵樹上的一截枝葉複製出一模一樣的一份之後扦插在另一段樹枝上！小方塊隨即展開一系列的實驗，而你，作為他的研究助理，需要幫他紀錄各種實驗數據。
一開始，小方塊有一棵樹，以 $N$ 個點、節點 1 為根的有根樹表示。接下來的 $Q$ 天，小方塊每天會給你兩種指令之一：
- 操作一：指定兩個節點 $a$、$b$，執行樹學技巧把以節點 $a$ 為根的子樹複製一份，變成節點 $b$ 的最後一個子節點。
- 操作二：指定兩個節點 $a$、$b$，請你紀錄這兩個節點在樹上距離幾條邊。
然而，因為樹的形狀會一直動來動去，所以小方塊指定一個節點的時候會給你一個數字，代表指定的節點在當時的那棵樹的 dfs 前序遍歷中的位置，由 1 開始編號；也就是說，一開始的根節點永遠都會是 1 號節點。小方塊跟你保證樹上的節點不會太多，免得 dfs 序數字太大了你記不住。小方塊偶爾會指定一個超過現有節點數量的數字，檢查你做實驗的時候有沒有在恍神，這時候你需要忽略這次操作並紀錄在實驗結果裡面。
不幸的是，實驗結束之後你把結果全部搞丟了，面臨被小方塊開除的危機。還好你還記得實驗過程中依序做了哪些操作，你能依據紀錄還原出實驗結果嗎？
Input Format
輸入第一行是一個整數 $N$，代表一開始的樹上節點數量。
接下來 $N - 1$ 行每行兩個整數，代表一開始的樹上的一條邊，節點編號代表 dfs 前序。
接下來的一行有一個整數 $Q$，代表操作數量。
接下來的 $Q$ 行，每行三個整數代表一次操作，形如：
1 a b：代表操作一2 a b：代表操作二
- $0 \leq N, Q \leq 2 \times 10^ 5$
- $1 \leq a, b \leq 10^ {18}$
- 一開始的 $N - 1$ 條邊形成一棵樹，而且節點編號形成合法的 dfs 序
- 保證操作過程中樹上節點數不超過 $10^ {18}$
Output Format
對每一次的操作二，輸出一行一個整數代表指定兩點的樹上距離。
對每一次指定到超過現有節點數的節點編號的操作（$a$ 或 $b$ 超過當時樹上的點數），包含操作一或操作二，輸出一行一個字串「:pensive:」並忽略該次操作。
Sample Input 1
6 1 2 2 3 1 4 4 5 4 6 10 1 1 48763 2 3 3 2 5 6 2 2 6 2 3 5 1 4 2 2 5 7 2 5 6 2 3 8 2 2 4
Sample Output 1
:pensive: 0 2 3 4 4 2 4 1
Sample Input 2
5 3 2 1 2 1 4 4 5 10 2 5 6 2 1 1 1 4 4 2 4 8 2 5 3 1 1 4 2 13 2 2 4 7 1 6 14 2 16 13
Sample Output 2
:pensive: 0 :pensive: 4 5 2 3
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 0~26 | 無額外限制。 | 100 |