753 . 歪皮有限公司

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

smgshabc123

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

100.0% (5/5)

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\sim N-1$ 之間唯一的編號代表。
接著的 $N-1$ 行，每行有兩個以一個空白隔開的整數 $a$ 與 $b$ ($0 \le a, b \le N-1$)，代表 $a$ 是 $b$ 的直屬上司。

假設 $S$ 是一次執行中所有測資的 $N$ 總和。
在 $10\%$ 的測資中，$2 \le S \le 100$ ，小 Y 最多有 $2$ 個直屬下屬，其他人最多一個直屬下屬。
其中 $40\%$ 的測資滿足，$2 \le S \le 100$。
其中 $70\%$ 的測資滿足，$2 \le S \le 2000$。
其中 $100\%$ 的測資滿足，$2 \le S \le 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\le S\le 100$，是個路徑 10
3 0~25 $2\le S\le 100$ 30
4 0~44 $2\le S\le 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