F - Farthest Pair Query 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 550 点

問題文

N 頂点の木があります。頂点には 1, 2, \ldots, N の番号が付けられており、i 番目の辺は頂点 U_i と頂点 V_i を結んでいます。

はじめ、すべての頂点は黒く塗られています。

以下のクエリを Q 個順に処理したときの各クエリの答えを求めてください。

  • 整数 x (1 \leq x \leq N) が与えられる。頂点 x が白く塗られているならば黒く、黒く塗られているならば白く塗り替える。その後、黒く塗られている頂点どうしの距離の最大値を求める。ただし、木上の 2 頂点間の距離とは、その 2 頂点を端点とする単純パスに含まれる辺の本数のことを指す。

なお、クエリを順に処理したとき、操作の過程で黒く塗られている頂点が常に 2 個以上存在するような入力のみが与えられます。

制約

  • 3 \leq N \leq 10^5
  • 1 \leq U_i, V_i \leq N
  • 与えられるグラフは木
  • 1 \leq Q \leq 10^5
  • 各クエリについて、1 \leq x \leq N
  • どの時点でも黒く塗られている頂点が 2 個以上存在する
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで \text{query}_i は i 番目のクエリを意味する。

N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

各クエリは以下の形式で与えられる。

x

出力

Q 行出力せよ。

i 行目には、クエリを順に処理したときの i 番目のクエリの答えを出力せよ。

入力例 1

7
1 2
2 3
2 4
6 7
3 5
7 3
9
1
4
2
6
3
1
1
4
6

出力例 1

4
3
3
2
2
3
2
3
4
  • 1 番目のクエリで色を塗り替えた後、黒く塗られている頂点は 2,3,4,5,6,7 です。 頂点 4 と頂点 6 の距離は 4 であり、答えは 4 です。
  • 2 番目のクエリで色を塗り替えた後、黒く塗られている頂点は 2,3,5,6,7 です。 頂点 2 と頂点 6 の距離は 3 であり、答えは 3 です。
  • 3 番目のクエリで色を塗り替えた後、黒く塗られている頂点は 3,5,6,7 です。 頂点 5 と頂点 6 の距離は 3 であり、答えは 3 です。
  • 4 番目のクエリで色を塗り替えた後、黒く塗られている頂点は 3,5,7 です。 頂点 5 と頂点 7 の距離は 2 であり、答えは 2 です。
  • 5 番目のクエリで色を塗り替えた後、黒く塗られている頂点は 5,7 です。 頂点 5 と頂点 7 の距離は 2 であり、答えは 2 です。
  • 6 番目のクエリで色を塗り替えた後、黒く塗られている頂点は 1,5,7 です。 頂点 1 と頂点 5 の距離は 3 であり、答えは 3 です。
  • 7 番目のクエリで色を塗り替えた後、黒く塗られている頂点は 5,7 です。 頂点 5 と頂点 7 の距離は 2 であり、答えは 2 です。
  • 8 番目のクエリで色を塗り替えた後、黒く塗られている頂点は 4,5,7 です。 頂点 4 と頂点 5 の距離は 3 であり、答えは 3 です。
  • 9 番目のクエリで色を塗り替えた後、黒く塗られている頂点は 4,5,6,7 です。 頂点 4 と頂点 6 の距離は 4 であり、答えは 4 です。

上に挙げた例は最大値を達成する一例であることに注意してください。

Score : 550 points

Problem Statement

There is a tree with N vertices. The vertices are numbered 1, 2, \ldots, N, and the i-th edge connects vertices U_i and V_i.

Initially, all vertices are painted black.

Process Q queries of the following form in order and find the answer for each query.

  • An integer x (1 \leq x \leq N) is given. If vertex x is white, repaint it black; if vertex x is black, repaint it white. Then, find the maximum distance between two black vertices. Here, the distance between two vertices on a tree is the number of edges in the simple path between them.

In the given inputs, there are always at least two black vertices when processing the queries in order.

Constraints

  • 3 \leq N \leq 10^5
  • 1 \leq U_i, V_i \leq N
  • The given graph is a tree.
  • 1 \leq Q \leq 10^5
  • For each query, 1 \leq x \leq N.
  • There are always at least two black vertices.
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \text{query}_i denotes the i-th query:

N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Each query is given in the following format:

x

Output

Output Q lines.

The i-th line should contain the answer for the i-th query when processed in order.

Sample Input 1

7
1 2
2 3
2 4
6 7
3 5
7 3
9
1
4
2
6
3
1
1
4
6

Sample Output 1

4
3
3
2
2
3
2
3
4
  • After the repainting in the 1st query, the black vertices are 2, 3, 4, 5, 6, 7. The distance between vertices 4 and 6 is 4, and the answer is 4.
  • After the repainting in the 2nd query, the black vertices are 2, 3, 5, 6, 7. The distance between vertices 2 and 6 is 3, and the answer is 3.
  • After the repainting in the 3rd query, the black vertices are 3, 5, 6, 7. The distance between vertices 5 and 6 is 3, and the answer is 3.
  • After the repainting in the 4th query, the black vertices are 3, 5, 7. The distance between vertices 5 and 7 is 2, and the answer is 2.
  • After the repainting in the 5th query, the black vertices are 5, 7. The distance between vertices 5 and 7 is 2, and the answer is 2.
  • After the repainting in the 6th query, the black vertices are 1, 5, 7. The distance between vertices 1 and 5 is 3, and the answer is 3.
  • After the repainting in the 7th query, the black vertices are 5, 7. The distance between vertices 5 and 7 is 2, and the answer is 2.
  • After the repainting in the 8th query, the black vertices are 4, 5, 7. The distance between vertices 4 and 5 is 3, and the answer is 3.
  • After the repainting in the 9th query, the black vertices are 4, 5, 6, 7. The distance between vertices 4 and 6 is 4, and the answer is 4.

Note that the examples given above are just one instance achieving the maximum value.