首先以1号结点为根建树，计算出每个结点的最大深度，再计算每个结点经过父结点路径的最长距离g[i]，g[i]=max(g[father],deep[brother]+2)
1 #include <iostream>
2 using namespace std;
3 const int OO=1000000;
4 int n;
5 int link[10001][2];
6 int dp[10001];
7 int g[10001];
8 int p[10001];
9 int q[10011],st,en;
10 void init(int a,int b){
11 if (link[a][0]==0) link[a][0]=b;
12 else{
13 int ns=link[a][0];
14 while (link[ns][1]!=0) ns=link[ns][1];
15 link[ns][1]=b;
16 }
17 }
18 void bfs(){
19 q[1]=1;
20 st=0; en=1;
21 while (st<en){
22 ++st;
23 int nx=q[st];
24 int ns=link[nx][0];
25 while (ns!=0){
26 ++en;
27 q[en]=ns;
28 ns=link[ns][1];
29 }
30 }
31 }
32 int main(){
33 scanf("%d",&n);
34 for (int i=2;i<=n;++i) scanf("%d",&p[i]);
35 for (int i=2;i<=n;++i) init(p[i],i);
36 bfs();
37 for (int i=n;i>0;--i){
38 int ii=q[i];
39 ++dp[ii];
40 if (dp[ii]>dp[p[ii]]) dp[p[ii]]=dp[ii];
41 --dp[ii];
42 }
43 dp[0]=0;
44 g[0]=-1;
45 for (int i=1;i<=n;++i){
46 int ii=q[i];
47 g[ii]=g[p[ii]]+1;
48 int ns=link[p[ii]][0];
49 while (ns!=0){
50 if (ns!=ii&&dp[ns]+2>g[ii]) g[ii]=dp[ns]+2;
51 ns=link[ns][1];
52 }
53 }
54 for (int i=1;i<=n;++i) if (g[i]>dp[i]) dp[i]=g[i];
55 int ans=OO;
56 for (int i=1;i<=n;++i) if (dp[i]<ans) ans=dp[i];
57 for (int i=1;i<=n;++i) if (dp[i]==ans) printf("%d ",i);
58 }
59
posted on 2008-11-07 17:38
Joseph 阅读(256)
评论(0) 编辑 收藏 引用