753 . 歪皮有限公司

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

peteryeee

User's AC Ratio

100.0% (8/8)

Submission's AC Ratio

75.0% (9/12)

Tags

apcsc apcsc-graph

Description

本題改寫自 2016 年 3 月 APCS 考古題。

小 Y 是歪皮有限公司的大老闆，這家公司有著嚴格的企業管理階層，每個員工都被指定了一個位階。此外，除了小 Y 以外的每個人都配有一個直屬上司，直屬上司的位階一定會比自己高。小 Y 是全公司位階最高的人。

因為有著這樣的特色，員工們彼此溝通喜歡透過直屬上司或直屬下屬傳話。舉例來說，下圖是公司直屬關係圖，在上面的節點表示位階較高者，連邊表示兩人有直屬關係。如果 1 號和 3 號員工需要傳話，1 號會通過直屬上司 4 號，4 號的直屬下屬 2 號，2 號的直屬下屬 3 號來完成，這中間經過 3 次傳話。

這樣的過程不盡然有效率，因此小 Y 想知道直屬關係最遠的兩個員工需要通過幾次傳話才能完成溝通。

Input Format

輸入包含多筆測資。

每筆測資中，
第一行為一個正整數 N 代表成員的個數，每人以 0∼N−1 之間唯一的編號代表。
接著的 N−1 行，每行有兩個以一個空白隔開的整數 a 與 b (0≤a,b≤N−1)，代表 a 是 b 的直屬上司。

假設 S 是一次執行中所有測資的 N 總和。
在 10% 的測資中，2≤S≤100 ，小 Y 最多有 2 個直屬下屬，其他人最多一個直屬下屬。
其中 40% 的測資滿足，2≤S≤100。
其中 70% 的測資滿足，2≤S≤2000。
其中 100% 的測資滿足，2≤S≤100000。

Output Format

每筆測資輸出一行，輸出兩名員工需要的最多傳話次數。

Sample Input 1

8
0 1
0 2
0 3
7 0
1 4
1 5
3 6
4
0 1
0 2
2 3

Sample Output 1

4
3

Hints

Problem Source

APCS 歷屆

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 1~6 2≤S≤100，是個路徑 10
3 0~25 2≤S≤100 30
4 0~44 2≤S≤2000 30
5 0~61 無額外限制 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 3 4 5
1 1000 524288 65536 2 3 4 5
2 1000 524288 65536 2 3 4 5
3 1000 524288 65536 2 3 4 5
4 1000 524288 65536 2 3 4 5
5 1000 524288 65536 2 3 4 5
6 1000 524288 65536 2 3 4 5
7 1000 524288 65536 3 4 5
8 1000 524288 65536 3 4 5
9 1000 524288 65536 3 4 5
10 1000 524288 65536 3 4 5
11 1000 524288 65536 3 4 5
12 1000 524288 65536 3 4 5
13 1000 524288 65536 3 4 5
14 1000 524288 65536 3 4 5
15 1000 524288 65536 3 4 5
16 1000 524288 65536 3 4 5
17 1000 524288 65536 3 4 5
18 1000 524288 65536 3 4 5
19 1000 524288 65536 3 4 5
20 1000 524288 65536 3 4 5
21 1000 524288 65536 3 4 5
22 1000 524288 65536 3 4 5
23 1000 524288 65536 3 4 5
24 1000 524288 65536 3 4 5
25 1000 524288 65536 3 4 5
26 1000 524288 65536 4 5
27 1000 524288 65536 4 5
28 1000 524288 65536 4 5
29 1000 524288 65536 4 5
30 1000 524288 65536 4 5
31 1000 524288 65536 4 5
32 1000 524288 65536 4 5
33 1000 524288 65536 4 5
34 1000 524288 65536 4 5
35 1000 524288 65536 4 5
36 1000 524288 65536 4 5
37 1000 524288 65536 4 5
38 1000 524288 65536 4 5
39 1000 524288 65536 4 5
40 1000 524288 65536 4 5
41 1000 524288 65536 4 5
42 1000 524288 65536 4 5
43 1000 524288 65536 4 5
44 1000 524288 65536 4 5
45 1000 524288 65536 5
46 1000 524288 65536 5
47 1000 524288 65536 5
48 1000 524288 65536 5
49 1000 524288 65536 5
50 1000 524288 65536 5
51 1000 524288 65536 5
52 1000 524288 65536 5
53 1000 524288 65536 5
54 1000 524288 65536 5
55 1000 524288 65536 5
56 1000 524288 65536 5
57 1000 524288 65536 5
58 1000 524288 65536 5
59 1000 524288 65536 5
60 1000 524288 65536 5
61 1000 524288 65536 5
Submit
Back to Top