Computer
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4159 Accepted Submission(s): 2078
Problem Description
A school bought the first computer some time ago(so this computer's id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.
Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4.
Input
Input file contains multiple test cases.In each case there is natural number N (N<=10000) in the first line, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 10^9. Numbers in lines of input are separated by a space.
Output
For each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N).
Sample Input
5 1 1 2 1 3 1 1 1
Sample Output
3
2
3
4
4
题目要求每一个点的最长路，可以用两次dfs解决，第一次dfs求出所有点和他子树中的点距离最远和次远的点和距离，然后第二次dfs时求出答案。。
对于一个点，如果他的父亲的最远点不在他的子树中，则他的最远点是他子树中最远的和他父亲的最远点的max，如果他父亲的最远点在他的子树中，则他的最远点是他子树中的最远点和他父亲的次远点的max，然后同时更新他的最远点和次远点
//ans[]表示一个点的最远点的距离,ans2[]表示一个点次远点的距离,
//dis[]表示一个点在其子树中最远点的距离,dis2[]表示一个点在其子树中次远点的距离
if (at[fa]==x){
if (ans2[fa]+e[i].s>dis[x]){
ans[x] = ans2[fa]+e[i].s;at[x] = fa;
ans2[x] = max(dis[x],dis2[x]);
}
else {
ans[x] = dis[x];at[x] = To[x];
ans2[x] = max(dis2[x],ans2[fa]+e[i].s);
}
}
else {
if (ans[fa]+e[i].s>dis[x]){
ans[x] = ans[fa]+e[i].s;at[x] = fa;
ans2[x] = max(dis[x],dis2[x]);
}
else {
ans[x] = dis[x];at[x] = To[x];
ans2[x] = max(dis2[x],ans[fa]+e[i].s);
}
}
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 20010
using namespace std;
struct data{int x,y,s,next;} e[3*N];
int dis[N],dis2[N],To[N],ans[N],ans2[N],at[N],n,x,y,s,a,b,cnt,head[N];
void Insert(int x,int y,int s){
e[++cnt].x = x;e[cnt].y = y;e[cnt].s = s;
e[cnt].next = head[x];head[x] = cnt;
}
void dfs1(int x,int fa){
dis[x] = dis2[x] = To[x] = 0;
for (int i=head[x];i;i=e[i].next)
if (e[i].y!=fa){
dfs1(e[i].y,x);
if (dis[e[i].y]+e[i].s>dis[x]){
dis2[x] = dis[x];
dis[x] = dis[e[i].y]+e[i].s;To[x] = e[i].y;
}
else if (dis[e[i].y]+e[i].s>dis2[x])
dis2[x] = dis[e[i].y]+e[i].s;
}
}
void dfs2(int x,int fa){
ans[x] = ans2[x] = at[x] = 0;
if (fa==-1){
ans[x] = dis[x];at[x] = To[x];
ans2[x] = dis2[x];
}
for (int i=head[x];i;i=e[i].next)
if (e[i].y==fa){
if (at[fa]==x){
if (ans2[fa]+e[i].s>dis[x]){
ans[x] = ans2[fa]+e[i].s;at[x] = fa;
ans2[x] = max(dis[x],dis2[x]);
}
else {
ans[x] = dis[x];at[x] = To[x];
ans2[x] = max(dis2[x],ans2[fa]+e[i].s);
}
}
else {
if (ans[fa]+e[i].s>dis[x]){
ans[x] = ans[fa]+e[i].s;at[x] = fa;
ans2[x] = max(dis[x],dis2[x]);
}
else {
ans[x] = dis[x];at[x] = To[x];
ans2[x] = max(dis2[x],ans[fa]+e[i].s);
}
}
}
for (int i=head[x];i;i=e[i].next)
if (e[i].y!=fa) dfs2(e[i].y,x);
}
int main(){
while (~scanf("%d",&n)){
memset(head,0,sizeof(head));
cnt = 0;
for (int i=2;i<=n;i++){
scanf("%d%d",&a,&b);
Insert(i,a,b);
Insert(a,i,b);
}
dfs1(1,-1);
dfs2(1,-1);
for (int i=1;i<=n;i++)
printf("%d\n",ans[i]);
}
}
评论 (0)
