URAL 1056(ツリーDP)
1056. Computer Net
Time limit: 2.0 second
Memory limit: 64 MB
Background
Computer net is created by consecutive computer plug-up to one that has already been connected to the net. Each new computer gets an ordinal number, but the protocol contains the number of its parent computer in the net. Thus, protocol consists of several numbers; the first of them is always 1, because the second computer can only be connected to the first one, the second number is 1 or 2 and so forth. The total quantity of numbers in the protocol is
N − 1 (
N is a total number of computers). For instance, protocol 1, 1, 2, 2 corresponds to the following net:
The distance between the computers is the quantity of mutual connections (between each other) in chain. Thus, in example mentioned above the distance between computers #4 and #5 is 2, and between #3 and #5 is 3.
Definition. Let the center of the net be the computer which has a minimal distance to the most remote computer. In the shown example computers #1 and #2 are the centers of the net.
Problem
Your task is to find all the centers using the set protocol.
Input
The first line of input contains an integer
N, the quantity of computers (2 ≤
N ≤ 10000). Successive
N − 1 lines contain protocol.
Output
Output should contain ordinal numbers of the determined net centers in ascending order.
Sample
input
output
标题:1番パソコンはルートノードで、2~n番パソコンの親ノードを与えて、それらのパソコンを中心にして、残りのパソコンまでの最大距離が最小であることを求める.
考え方:一点からすべてのサブノードまでの最大距離は求めやすいが、親ノードを通じて到達できる最大距離も知らなければならないので、まず処理して、すべての点からそのサブノードまでの最大距離辺と次大距離辺を求めて、それから各ノードがその親ノードの最大距離辺にあるかどうかを分析して、もしあるならば、親ノードの二次大距離でノードを更新します.そうしないと、親ノードの最大距離で更新されます.
Time limit: 2.0 second
Memory limit: 64 MB
Background
Computer net is created by consecutive computer plug-up to one that has already been connected to the net. Each new computer gets an ordinal number, but the protocol contains the number of its parent computer in the net. Thus, protocol consists of several numbers; the first of them is always 1, because the second computer can only be connected to the first one, the second number is 1 or 2 and so forth. The total quantity of numbers in the protocol is
N − 1 (
N is a total number of computers). For instance, protocol 1, 1, 2, 2 corresponds to the following net:
1 - 2 - 5
| |
3 4
The distance between the computers is the quantity of mutual connections (between each other) in chain. Thus, in example mentioned above the distance between computers #4 and #5 is 2, and between #3 and #5 is 3.
Definition. Let the center of the net be the computer which has a minimal distance to the most remote computer. In the shown example computers #1 and #2 are the centers of the net.
Problem
Your task is to find all the centers using the set protocol.
Input
The first line of input contains an integer
N, the quantity of computers (2 ≤
N ≤ 10000). Successive
N − 1 lines contain protocol.
Output
Output should contain ordinal numbers of the determined net centers in ascending order.
Sample
input
output
5
1
1
2
2
1 2
标题:1番パソコンはルートノードで、2~n番パソコンの親ノードを与えて、それらのパソコンを中心にして、残りのパソコンまでの最大距離が最小であることを求める.
考え方:一点からすべてのサブノードまでの最大距離は求めやすいが、親ノードを通じて到達できる最大距離も知らなければならないので、まず処理して、すべての点からそのサブノードまでの最大距離辺と次大距離辺を求めて、それから各ノードがその親ノードの最大距離辺にあるかどうかを分析して、もしあるならば、親ノードの二次大距離でノードを更新します.そうしないと、親ノードの最大距離で更新されます.
#include<stdio.h>
#include<string.h>
const int N=10001;
int dp[N][2],vis[N],head[N],num,ans;
struct edge
{
int st,ed,next;
}e[N*4];
void addedge(int x,int y)
{
e[num].st=x;e[num].ed=y;e[num].next=head[x];head[x]=num++;
e[num].st=y;e[num].ed=x;e[num].next=head[y];head[y]=num++;
}
void dfs1(int u)
{
vis[u]=1;
int i,v;
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].ed;
if(vis[v]==1)continue;
dfs1(v);
if(dp[v][1]+1>dp[u][1])
{
dp[u][0]=dp[u][1];
dp[u][1]=dp[v][1]+1;
}
else if(dp[v][1]+1>dp[u][0])
dp[u][0]=dp[v][1]+1;
}
}
void dfs2(int u)
{
vis[u]=1;
int i,v,temp;
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].ed;
if(vis[v]==1)continue;
if(dp[u][1]==dp[v][1]+1)//
temp=dp[u][0]+1;
else temp=dp[u][1]+1;
if(temp>dp[v][1]) // v ，
{
dp[v][0]=dp[v][1];
dp[v][1]=temp;
}
else if(temp>dp[v][0])
{
dp[v][0]=temp;
}
if(ans>dp[v][1])
ans=dp[v][1];
dfs2(v);
}
}
int main()
{
int n,i,x;
while(scanf("%d",&n)!=-1)
{
memset(head,-1,sizeof(head));
memset(dp,0,sizeof(dp));
num=0;
for(i=2;i<=n;i++)
{
scanf("%d",&x);
addedge(i,x);
}
ans=99999999;
memset(vis,0,sizeof(vis));
dfs1(1);
memset(vis,0,sizeof(vis));
dfs2(1);
if(ans>dp[1][1])ans=dp[1][1];
for(i=1;i<=n;i++)
{
if(dp[i][1]==ans)
printf("%d ",i);
}
printf("
");
}
return 0;
}