263 . 小風愛種樹

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Fysty

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

ioicamp ioicamp-2020

Description

小風是個環保的人，他很喜歡種樹。

一開始這棵樹有 N 個節點，接下來 Q 天每天都會有一個新的節點長出來，並接在其中一個存在的節點上面，請在每天長出節點後都告訴小風當前樹上最長的路徑長度。

Input Format

第一行給定兩個正整數 N,Q。

接下來 N−1 行每行給定兩個正整數 ui,vi，代表編號為 ui 的點與編號為 vi 的點之間有一條邊。

接下來 Q 行，每行給定一個整數 xi，代表第 i 天長出了一個編號為 i+N 的點，它與編號為 xi⊕L 的點之間有一條邊，其中 L 為上一筆詢問的答案（若這是第一筆詢問則 L=0），而 ⊕ 為 bitwise xor。

  • 1≤N≤2×105
  • 1≤Q≤3×105
  • 1≤ui,vi≤N
  • 1≤(xi⊕L)<i+N

Output Format

請輸出 Q 行，每行有一個數字代表當前樹上最長的路徑長度（所經過的邊數）

Sample Input 1

5 3
1 2
2 3
1 4
4 5
3
3
3

Sample Output 1

5
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 262144 65536 1 2
1 4000 262144 65536 2
2 4000 262144 65536 2
3 4000 262144 65536 2
4 4000 262144 65536 2
5 4000 262144 65536 2
6 4000 262144 65536 2
7 4000 262144 65536 2
8 4000 262144 65536 2
9 4000 262144 65536 2
10 4000 262144 65536 2
11 4000 262144 65536 2
12 4000 262144 65536 2
13 4000 262144 65536 2
14 4000 262144 65536 2
15 4000 262144 65536 2
16 4000 262144 65536 2
17 4000 262144 65536 2
18 4000 262144 65536 2
19 4000 262144 65536 2
20 4000 262144 65536 2
21 4000 262144 65536 2
22 4000 262144 65536 2
23 4000 262144 65536 2
24 4000 262144 65536 2
25 4000 262144 65536 2
Submit
Back to Top