120 . 樹直徑

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

53.8% (7/13)

Tags

ioicamp ioicamp-2023

Description

小風手上有一棵 $N$ 個點的樹，顧名思義，它有 $N - 1$ 條邊連接著 $N$ 個點，使得任意兩個點都可以透過若干條邊抵達，節點以 $1$ 至 $N$ 編號。

小風覺得這棵樹太長了，所以他想進行如下操作一次：砍掉樹上的其中一條邊，再另外加上一條邊回去使其保持連通。小風想要透過這個操作減少樹的直徑，請問小風可以透過這個操作讓樹直徑最小為何？

對任意兩點，我們定義其距離為這個個點之間唯一路徑的邊數，對一個樹我們定義其直徑為任意兩點之間距離的最大值。

Input Format

輸入第一行只有一個正整數 $N$，代表樹上節點的個數。

接下來有 $N - 1$ 行，第 $i$ 行有兩個正整數 $u_i$, $v_i$ 以空白分開，代表第 $i$ 條邊連接的兩個節點編號。

  • $2 \leq N \leq 5 \times 10^ 5$
  • $1 \leq u_i, v_i \leq N$
  • 輸入保證形成一個樹

Output Format

請輸出一個正整數於一行代表答案。

Sample Input 1

5
5 1
4 1
5 3
2 3

Sample Output 1

3

Sample Input 2

6
6 5
1 3
3 2
4 5
6 3

Sample Output 2

3

Sample Input 3

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

Sample Output 3

4

Hints

Problem Source

IOICamp 2023 Day4 pC

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~30 $N \leq 50$ 20
3 0~59 $N \leq 1000$ 30
4 0~89 無其他限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 524288 65536 1 2 3 4
1 4000 524288 65536 1 2 3 4
2 4000 524288 65536 1 2 3 4
3 4000 524288 65536 2 3 4
4 4000 524288 65536 2 3 4
5 4000 524288 65536 2 3 4
6 4000 524288 65536 2 3 4
7 4000 524288 65536 2 3 4
8 4000 524288 65536 2 3 4
9 4000 524288 65536 2 3 4
10 4000 524288 65536 2 3 4
11 4000 524288 65536 2 3 4
12 4000 524288 65536 2 3 4
13 4000 524288 65536 2 3 4
14 4000 524288 65536 2 3 4
15 4000 524288 65536 2 3 4
16 4000 524288 65536 2 3 4
17 4000 524288 65536 2 3 4
18 4000 524288 65536 2 3 4
19 4000 524288 65536 2 3 4
20 4000 524288 65536 2 3 4
21 4000 524288 65536 2 3 4
22 4000 524288 65536 2 3 4
23 4000 524288 65536 2 3 4
24 4000 524288 65536 2 3 4
25 4000 524288 65536 2 3 4
26 4000 524288 65536 2 3 4
27 4000 524288 65536 2 3 4
28 4000 524288 65536 2 3 4
29 4000 524288 65536 2 3 4
30 4000 524288 65536 2 3 4
31 4000 524288 65536 3 4
32 4000 524288 65536 3 4
33 4000 524288 65536 3 4
34 4000 524288 65536 3 4
35 4000 524288 65536 3 4
36 4000 524288 65536 3 4
37 4000 524288 65536 3 4
38 4000 524288 65536 3 4
39 4000 524288 65536 3 4
40 4000 524288 65536 3 4
41 4000 524288 65536 3 4
42 4000 524288 65536 3 4
43 4000 524288 65536 3 4
44 4000 524288 65536 3 4
45 4000 524288 65536 3 4
46 4000 524288 65536 3 4
47 4000 524288 65536 3 4
48 4000 524288 65536 3 4
49 4000 524288 65536 3 4
50 4000 524288 65536 3 4
51 4000 524288 65536 3 4
52 4000 524288 65536 3 4
53 4000 524288 65536 3 4
54 4000 524288 65536 3 4
55 4000 524288 65536 3 4
56 4000 524288 65536 3 4
57 4000 524288 65536 3 4
58 4000 524288 65536 3 4
59 4000 524288 65536 3 4
60 4000 524288 65536 4
61 4000 524288 65536 4
62 4000 524288 65536 4
63 4000 524288 65536 4
64 4000 524288 65536 4
65 4000 524288 65536 4
66 4000 524288 65536 4
67 4000 524288 65536 4
68 4000 524288 65536 4
69 4000 524288 65536 4
70 4000 524288 65536 4
71 4000 524288 65536 4
72 4000 524288 65536 4
73 4000 524288 65536 4
74 4000 524288 65536 4
75 4000 524288 65536 4
76 4000 524288 65536 4
77 4000 524288 65536 4
78 4000 524288 65536 4
79 4000 524288 65536 4
80 4000 524288 65536 4
81 4000 524288 65536 4
82 4000 524288 65536 4
83 4000 524288 65536 4
84 4000 524288 65536 4
85 4000 524288 65536 4
86 4000 524288 65536 4
87 4000 524288 65536 4
88 4000 524288 65536 4
89 4000 524288 65536 4
Submit
Back to Top