随笔 - 32  文章 - 2  trackbacks - 0
<2008年11月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

常用链接

留言簿(3)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 8797
  • 排名 - 1247

最新评论

阅读排行榜

评论排行榜

首先以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 阅读(257) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理