鏈接：
http://acm.hdu.edu.cn/showproblem.php?pid=2196
https://blog.csdn.net/shuangde800/article/details/9732825
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long int64;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int MAXN = 10010;
struct Node
{
int v, w;
};
vector<Node>adj[MAXN];
int indeg[MAXN];
int val[MAXN];
int n, m;
int64 f[MAXN][2];
int vis[MAXN];
int64 dfs1(int u) //從自己開始
{vis[u]=true; //標記自己f[u][0] = 0; //自己到原點的距離初始化0；for(int i=0;i<adj[u].size();++i)//自己到每個點的距離取最大值
{int v = adj[u][i].v; //節點int w = adj[u][i].w; //到節點的權值if(vis[v]) //被標記跳過continue;f[u][0]=max(f[u][0],dfs1(v)+w);//自己到原點的最大距離=自己到原點的距離節點到自己的距離加上自己到誰大
}return f[u][0];//返回節點到自己的距離
}
void dfs2(int u, int fa_w)
{vis[u] = true;//標記自己int max1=0, v1, max2=0, v2; //初始化for(int i=0; i<adj[u].size(); ++i){int v=adj[u][i].v; //節點int w=adj[u][i].w; //到節點的權值if(vis[v])continue; //被標記跳過int tmp=f[v][0]+w; //距離為目標節點到葉子加上自己到節點的權值。if(tmp>max1) //（第一次t）如果下一個子節點距離更長
{max2=max1; //（第一次為0）賦上次值v2=v1; //（第一次。。） 為次節點max1=tmp; //（第一次為目標節點到葉子加上自己到節點的權值。）v1=v; //（第一次為目標權值）
}else if(tmp==max1||tmp>max2) //如果與次值相等或者比次值大
{max2=tmp;//次值等于這個值 。v2=v;//次值節點為次節點。
}}if(u!= 1) //如果不為根節點
{int tmp = f[u][1];//除去子節點最長距離的子節點最長距離int v = -1;//目標節點為-1；if(tmp > max1){max2=max1;v2=v1;max1=tmp;v1=v;}else if(tmp==max1||tmp>max2){max2=tmp;v2=v;}}for(int i=0; i<adj[u].size(); ++i){int v=adj[u][i].v;int w=adj[u][i].w;if(vis[v])continue;if(v==v1){f[v][1] = max2 + w;}else{f[v][1] = max1 + w;}dfs2(v, w);}
}
int main()
{while(~scanf("%d", &n) && n){for(int i=1;i<=n;++i)adj[i].clear();for(int u=2;u<=n;++u){int v,w;scanf("%d%d", &v, &w);adj[u].push_back((Node){v,w}); //裝入目標節點，權值adj[v].push_back((Node){u,w}); //裝入自己，權值
}memset(f, 0, sizeof(f));memset(vis, 0, sizeof(vis));dfs1(1);memset(vis, 0, sizeof(vis));dfs2(1, 0);for(int i=1; i<=n; ++i){cout<<max(f[i][0],f[i][1])<<endl;}
}
return 0;
} ?
