263 . 小風愛種樹
TopCoder
Tags
Description
小風是個環保的人，他很喜歡種樹。
一開始這棵樹有 $N$ 個節點，接下來 $Q$ 天每天都會有一個新的節點長出來，並接在其中一個存在的節點上面，請在每天長出節點後都告訴小風當前樹上最長的路徑長度。
Input Format
第一行給定兩個正整數 $N, Q$。
接下來 $N - 1$ 行每行給定兩個正整數 $u_i, v_i$，代表編號為 $u_i$ 的點與編號為 $v_i$ 的點之間有一條邊。
接下來 $Q$ 行，每行給定一個整數 $x_i$，代表第 $i$ 天長出了一個編號為 $i + N$ 的點，它與編號為 $x_i \oplus L$ 的點之間有一條邊，其中 $L$ 為上一筆詢問的答案（若這是第一筆詢問則 $L = 0$），而 $\oplus$ 為 bitwise xor。
- $1 \leq N \leq 2 \times 10^ 5$
- $1 \leq Q \leq 3 \times 10^ 5$
- $1 \leq u_i, v_i \leq N$
- $1 \leq (x_i \oplus L) < i + N$
Output Format
請輸出 $Q$ 行，每行有一個數字代表當前樹上最長的路徑長度（所經過的邊數）
Sample Input 1
5 3
1 2
2 3
1 4
4 5
3
3
3
1 2
2 3
1 4
4 5
3
3
3
Sample Output 1
5
6
7
6
7
Hints
在範例測資中，以下為每天會發生的事情：
- 第 $1$ 天，樹長出了一個編號為 $6$ 的點，並接在 $3$ 的上面。
- 第 $2$ 天，樹長出了一個編號為 $7$ 的點，並接在 $6$ 的上面。
- 第 $3$ 天，樹長出了一個編號為 $8$ 的點，並接在 $5$ 的上面。
Problem Source
IOICamp 2020 Day4 pG
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~25 | 無額外限制 | 100 |