1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
|
#include <cstdio>
struct list{
int father,length,child,next;
int max1,where,max2;
};
int n;
list tree[10001];
int max(int x,int y) {
if (x>y) return(x);
return(y);
}
void init() {
scanf("%d\n",&n);
for (int i=2;i<=n;i++) {
scanf("%d%d\n",&tree[i].father,&tree[i].length);
tree[i].next=tree[tree[i].father].child;
tree[tree[i].father].child=i;
}
}
void dfs(int num) {
int childnum=tree[num].child;
while (childnum!=0) {
dfs(childnum);
if (tree[childnum].max1+tree[childnum].length>tree[num].max1) {
tree[num].max2=tree[num].max1;
tree[num].max1=tree[childnum].max1+tree[childnum].length;
tree[num].where=childnum;
}
else if (tree[childnum].max1+tree[childnum].length>tree[num].max2)
tree[num].max2=tree[childnum].max1+tree[childnum].length;
childnum=tree[childnum].next;
}
}
void work() {
dfs(1);
for (int i=1;i<=n;i++) {
int temp1=i,sum=0,ans=tree[i].max1;
while (tree[temp1].father!=0) {
sum+=tree[temp1].length;
if (tree[tree[temp1].father].where!=temp1)
ans=max(ans,tree[tree[temp1].father].max1+sum);
else
ans=max(ans,tree[tree[temp1].father].max2+sum);
temp1=tree[temp1].father;
}
printf("%d\n",ans);
}
}
int main() {
init();
work();
}
|