treeDP：
#include<iostream>
using namespace std;
int N;
int father[10100];
int pre[10100],son[10100],now[10100]={0};
int down[10100][2]={0};
int up[10100]={0};
void dfs(int x){
int Now=now[x];
while(Now>0){
int k=son[Now];
dfs(k);
if(down[k][1]+1>down[x][1]){
down[x][0]=down[x][1]; //次优值
down[x][1]=down[k][1]+1; //最优值
}
else if(down[k][1]+1>down[x][0])
down[x][0]=down[k][1]+1;
Now=pre[Now];
}
}
void treedp(int x){
if(x==1) up[x]=0;
else{
up[x]=up[father[x]]+1;
int tmp;
if(down[father[x]][1]==down[x][1]+1) //当father[x]的最优值是从x来的，则从另一条取值
tmp=down[father[x]][0]+1;
else tmp=down[father[x]][1]+1;
if(tmp>up[x])
up[x]=tmp;
}
while(now[x]){
treedp(son[now[x]]);
now[x]=pre[now[x]];
}
}
int main()
{
cin>>N;
int c=0,x;
for(int i=2;i<=N;++i){
cin>>x;
father[i]=x;
++c; pre[c]=now[x]; son[c]=i; now[x]=c;
}
dfs(1);
treedp(1);
int Min=0xFFFFFFF,ch1,ch2;
for(int i=1;i<=N;++i){
int tmp=max(up[i],down[i][1]);
if(Min>tmp){
Min=tmp;
ch1=i;
ch2=0;
}
else if(Min==tmp)
ch2=i;
}
cout<<ch1;
if(ch2) cout<<" "<<ch2;
cout<<endl;
return 0;
}
BFS:
#include<iostream>
using namespace std;
int N;
int que[20001];
int dis[20001]={0};
int a[20001];
int pre[20001]={0};
bool vis[20001]={0};
int mx=0,mx2=0,mxi,mx2i;
int main()
{
cin>>N;
for(int i=2;i<=N;++i)
cin>>a[i];
que[1]=1;
int h=1,t=1;
while(h<=t){
for(int i=1;i<=N;++i)
if(a[i]==que[h]&&dis[i]==0){
dis[i]=dis[que[h]]+1;
if(dis[i]>mx){
mx=dis[i];
mxi=i;
}
que[++t]=i;
}
h++;
}
memset(dis,0,sizeof(dis));
que[1]=mxi;
vis[mxi]=1;
h=t=1;
while(h<=t){
int x=que[h];
if(x!=1&&!vis[a[x]]){
que[++t]=a[x];
dis[a[x]]=dis[x]+1;
pre[a[x]]=x;
vis[a[x]]=1;
if(dis[a[x]]>mx2){
mx2=dis[a[x]];
mx2i=a[x];
}
}
for(int i=1;i<=N;++i)
if(a[i]==x&&dis[i]==0&&!vis[i]){
dis[i]=dis[x]+1;
pre[i]=x;
vis[i]=1;
if(dis[i]>mx2){
mx2=dis[i];
mx2i=i;
}
que[++t]=i;
}
h++;
}
int i=pre[mx2i]; t=0;
while(i!=mxi){
++t;
i=pre[i];
}
if(t==0)
cout<<mx2i<<" "<<mxi;
i=pre[mx2i];
int p,q;
if(t%2){
p=(t/2)+1;
q=0;
}
else{
p=t/2;
q=p+1;
}
t=0;
while(i!=mxi){
++t;
if(t==p) cout<<i;
if(t==q) cout<<" "<<i;
i=pre[i];
}
cout<<endl;
return 0;
}
posted on 2009-06-04 20:15
xfstart07 阅读(212)
评论(0) 编辑 收藏 引用 所属分类:
代码库