所謂樹的核，就是樹的中心
中心是指到其它節點距離的最大值最小的節點
1 - 2 - 5
| |
3 4
樣例里的1和2就是這個樹的中心……
本題是要找出樹的所有中心
由于時限2S，ural的機器又快，節點數不過10000，N^2枚舉+DFS驗證是無壓力的……
但是身為一個有志青年，是不能輕言滿足的……
由于無根樹不好辦事，我們不妨令根為1；
然后采用兩遍DFS的方法
第一次從根開始DFS，處理每個頂點最多能夠沿DFS的方向走多遠，直接DFS就行
（在下面程序保存為rdeep）
這一部分處理完了，接下來的部分是每個頂點向該點的父節點反著走，能走多遠
（在下面程序保存為fdeep）
這里的處理方法是這樣：假設現在是這樣：A的父親為FA，有子節點B，C，D，沿著B向下DFS能走距離Db，C：Dc，D：Dd；
那么由B反著走到A，然后再往遠走，最遠能到哪里呢？……有3個選擇，沿著FA向上，沿著C向下，沿著D向下
選擇一個最長的就行了；
假設某個節點的子節點數很多，實際上只用保留兩種情況：能走最遠的字節點，以及能走第二遠的字節點；
其他字節點都往該節點父節點或者最遠的子節點走；最遠的那個往該節點父節點或者第二遠的子節點走；
代碼如下：
1 class Prob {
2 //臨接表
3 ArrayList< LinkedList<Integer> > adj;
4 //加速控制臺IO
5 BufferedReader br = new BufferedReader(
6 new InputStreamReader(System.in));
7
8 //計算正向DFS的最遠深度
9 int[] rdeep;
10 int dfs(int now,int fa) {
11 for (Integer i : adj.get(now)) {
12 if (i == fa) continue;
13 int tmp = dfs(i,now);
14 if (tmp > rdeep[now]) {
15 rdeep[now] = tmp;
16 }
17 }
18 return rdeep[now] + 1;
19 }
20
21 //反向DFS的深度
22 int[] fdeep;
23 //falen是從當前節點向FA反過去走能到的最遠距離
24 void dfs(int now,int fa,int faLen) {
25 //找順著走最遠的子節點
26 int fIND = -1;
27 for (Integer i : adj.get(now)) {
28 if (i == fa) continue;
29 if (fIND == -1 || rdeep[i] > rdeep[fIND]) {
30 fIND = i;
31 }
32 }
33 //找不到，當前就是葉子節點，退出
34 if (fIND == -1) {
35 fdeep[now] = faLen;
36 return;
37 }
38 //找第二遠的節點
39 int sIND = -1;
40 for (Integer i : adj.get(now)) {
41 if (i == fa) continue;
42 if (i == fIND) continue;
43 if (sIND == -1 || rdeep[i] > rdeep[sIND]) {
44 sIND = i;
45 }
46 }
47 //沒有第二遠，只能向FA反向走
48 if (sIND == -1) {
49 fdeep[now] = faLen;
50 dfs(fIND,now,faLen+1);
51 return;
52 }
53 //向最遠的走或者向FA走哪個更遠
54 int v1 = rdeep[fIND] + 1 > faLen ? rdeep[fIND] + 1 : faLen;
55 //向第二遠的走或向FA走哪個更遠
56 int v2 = rdeep[sIND] + 1 > faLen ? rdeep[sIND] + 1 : faLen;
57
58 //更新當前faLen
59 fdeep[now] = faLen > v1? faLen : v1;
60 fdeep[now] = fdeep[now] > v2? fdeep[now] : v2;
61
62 //更新子節點
63 for (Integer i : adj.get(now)) {
64 if (i == fa) continue;
65 //最遠的那個子節點：沿著第二個走
66 //其他沿著最遠的走
67 if (i == fIND) {
68 dfs(i,now,v2+1);
69 } else {
70 dfs(i,now,v1+1);
71 }
72 }
73 }
74
75
76 void solve() throws IOException {
77 //讀入
78 int n = Integer.parseInt(br.readLine());
79 adj = new ArrayList< LinkedList<Integer> >();
80 rdeep = new int[n+1];
81 fdeep = new int[n+1];
82 for (int i = 0; i <= n; i++) {
83 adj.add(new LinkedList<Integer>());
84 }
85 for (int i = 2; i <= n; i++) {
86 int j = Integer.parseInt(br.readLine());
87 adj.get(i).add(j);
88 adj.get(j).add(i);
89 }
90 dfs(1,0);
91 dfs(1,0,0);
92 Set<Integer> ans = new TreeSet<Integer>();
93 int now = n + n;
94 // debug(fdeep);
95 // debug(rdeep);
96 //按要求從小到大輸出所有答案
97 for (int i = 1; i <= n; i++) {
98 int deep = fdeep[i] > rdeep[i] ? fdeep[i] : rdeep[i];
99 if (deep < now) {
100 now = deep;
101 ans.clear();
102 }
103 if (deep == now) {
104 ans.add(i);
105 }
106 }
107 for (Integer i: ans) {
108 System.out.print(i + " ");
109 }
110 }
111 void debug(Object x) {
112 System.err.println(Arrays.deepToString(x));
113 }
114 }
|