/*
两种做法
1.求出树直径v1,v2，那么有一个性质：任取一点u，树上到u距离最远的点必定是v1或v2
那么可以一次dfs求树v1
第二次求dis1[],求出所有点到v1的距离，同时求出v2
第三次求出dis2[],求出所有点到v2的距离
2.树形dp，dp[u][0|1]表示结点u向下的最大距离和向上的最大距离
dp[u][0]可以直接由子树求出
dp[u][1]应该从父节点推到子节点，如果v是u的大儿子，那么dp[v][1]=max(sec,dp[u][1])+e[i].w;
否则就是dp[v][1]=max(Max,dp[u][1])+e[i].w
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
struct Edge{
int to,nxt,w;}edge[maxn<<
1];
int head[maxn],tot,n;
long long dp[maxn][
2];
void init(){
memset(head,-
1,
sizeof head);
tot=
0;
}
void addedge(
int u,
int v,
int w){
edge[tot].to=v;edge[tot].w=w;edge[tot].nxt=head[u];head[u]=tot++
;
}
void dfs0(
int u,
int pre){
dp[u][0]=
0;
for(
int i=head[u];i!=-
1;i=
edge[i].nxt){
int v=
edge[i].to;
if(v!=
pre){
dfs0(v,u);
dp[u][0]=max(dp[u][
0],dp[v][
0]+
edge[i].w);
}
}
}
void dfs1(
int u,
int pre){
long long Max=
0,Sec=
0,v1,v2;
//u的大儿子下标，二儿子下标
for(
int i=head[u];i!=-
1;i=edge[i].nxt){
//这个循环处理出u的大儿子
int v=
edge[i].to;
if(v==pre)
continue;
int tmp=edge[i].w+dp[v][
0];
if(tmp>Max){
//找到了更大的儿子树
Sec=Max,Max=
tmp;
v2=v1,v1=
v;
}
else if(tmp==Max || tmp>
Sec)
Sec=tmp,v2=
v;
}
//printf("%d %d\n",u,Max);
if(u!=-
1){
//和u的上面进行比较
long long tmp=dp[u][
1],v=-
1;
if(tmp>Max){
//找到了更大的儿子树
Sec=Max,Max=
tmp;
v2=v1,v1=
v;
}
else if(tmp==Max || tmp>
Sec)
Sec=tmp,v2=
v;
}
for(
int i=head[u];i!=-
1;i=edge[i].nxt){
//这个循环求dp进行递归
int v=
edge[i].to;
if(v==pre)
continue;
if(v==v1)dp[v][
1]=Sec+
edge[i].w;
else dp[v][
1]=Max+
edge[i].w;
dfs1(v,u);
}
//printf("%d %d\n",u,Max);
}
int main(){
while(cin>>
n){
init();
for(
int v=
2;v<=n;v++
){
int u,w;
cin>>u>>
w;
addedge(u,v,w);
addedge(v,u,w);
}
memset(dp,0,
sizeof dp);
dfs0(1,
0);dfs1(
1,
0);
for(
int i=
1;i<=n;i++
)
printf("%lld\n",max(dp[i][
0],dp[i][
1]));
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10333946.html
