F - Centipede Graph 解説 /

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

配点 : 500 点

問題文

頂点に 1 から N の番号がついた N 頂点の木 T が与えられます。i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。

正整数 k について「長さ k のムカデグラフ」を以下の手順で得られる頂点数 3k のグラフと定義します。

  • 頂点数 k のパスグラフを用意する。
  • そのパスグラフの各頂点 v に対して、v のみに隣接する 2 つの頂点を新たに追加する。

例えば、長さ 4 のムカデグラフは下図のようになります。

木 T の部分グラフとして含まれる「長さ x のムカデグラフ」のうち、最大の x を求めて下さい。

Q 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \le Q
  • 3 \le N \le 2 \times 10^5
  • 1 \le A_i, B_i \le N
  • 与えられるグラフは木
  • 全てのテストケースにおける N の総和は 2 \times 10^5 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

Q
\text{case}_1
\text{case}_2
\vdots
\text{case}_Q

各テストケースは以下の形式で与えられる。

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

出力

Q 行出力せよ。

i 行目には i 番目のテストケースについて、答えを出力せよ。

入力例 1

3
8
1 3
2 4
2 5
2 6
3 5
4 7
5 8
5
1 5
1 2
1 3
3 4
15
13 3
4 13
11 1
14 9
9 13
13 6
1 10
7 9
13 2
10 5
3 12
15 13
9 10
12 8

出力例 1

2
1
3

1 番目のテストケースについて、頂点 2,3,4,5,6,8 の 6 頂点からなるグラフは「長さ 2 のムカデグラフ」となっています。

長さ 3 以上のムカデグラフは部分グラフに含まれないため、答えは 2 です。よって 2 と出力してください。

Score : 500 points

Problem Statement

You are given a tree T with N vertices numbered 1 to N. The i-th edge connects vertices A_i and B_i.

For a positive integer k, define a "centipede graph of length k" as a graph with 3k vertices obtained by the following procedure:

  • Prepare a path graph with k vertices.
  • For each vertex v of the path graph, add two new vertices adjacent only to v.

For example, a centipede graph of length 4 is as shown in the figure below.

Find the maximum x such that a "centipede graph of length x" is contained as a subgraph of tree T.

Q test cases are given; solve each of them.

Constraints

  • 1 \le Q
  • 3 \le N \le 2 \times 10^5
  • 1 \le A_i, B_i \le N
  • The given graph is a tree.
  • The sum of N over all test cases is at most 2 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

Q
\text{case}_1
\text{case}_2
\vdots
\text{case}_Q

Each test case is given in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

Output

Output Q lines.

The i-th line should contain the answer for the i-th test case.

Sample Input 1

3
8
1 3
2 4
2 5
2 6
3 5
4 7
5 8
5
1 5
1 2
1 3
3 4
15
13 3
4 13
11 1
14 9
9 13
13 6
1 10
7 9
13 2
10 5
3 12
15 13
9 10
12 8

Sample Output 1

2
1
3

For the first test case, the graph consisting of the six vertices 2,3,4,5,6,8 forms a "centipede graph of length 2".

No centipede graph of length 3 or more is contained as a subgraph, so the answer is 2. Thus, output 2.