所谓树的核，就是树的中心
中心是指到其它节点距离的最大值最小的节点
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 }
|