HDU2196(Computer经典换根dp求一棵树中所有节点能达到的最长距离)

题目
博主讲的很好&＃xff1a;https://blog.csdn.net/u013480600/article/details/21831363

#include
#define en &＃39;\n&＃39;
#define m(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N&＃61;1e4&＃43;5;
struct Edge{int to;ll len;int nex;}edge[N<<1];
int head[N],tot;
inline void add(int from,int to,ll len){edge[&＃43;&＃43;tot]&＃61;(Edge){to,len,head[from]};head[from]&＃61;tot;edge[&＃43;&＃43;tot]&＃61;(Edge){from,len,head[to]};head[to]&＃61;tot;
}
ll dp[N][3];int son[N];//dp[x][0]:节点x正向最大距离 son[x]:节点x正向最大距离经过的儿子
void dfs1(int x,int fa){//dp[x][1]:节点不经过son[x]经过其他儿子的最大距离 dp[x][2]:节点x经过其父亲的反向最大距离dp[x][0]&＃61;dp[x][1]&＃61;dp[x][2]&＃61;0;for(int i&＃61;head[x];i;i&＃61;edge[i].nex){int y&＃61;edge[i].to;ll w&＃61;edge[i].len;if(y&＃61;&＃61;fa) continue;dfs1(y,x);if(dp[x][0]<dp[y][0]&＃43;w){//son[x]这个儿子要被换掉 所以次大距离也可被之前的son[x]的最大距离更新 因为son[x]马上不是之前的那个儿子了dp[x][1]&＃61;max(dp[x][1],dp[x][0]);dp[x][0]&＃61;dp[y][0]&＃43;w,son[x]&＃61;y;}else dp[x][1]&＃61;max(dp[x][1],dp[y][0]&＃43;w);//这个儿子不是正向最大距离经过的儿子 也可以用来看能否更新dp[x][1].}
}
void dfs2(int x,int fa){//dfs2函数是为了得到dp[x][2]for(int i&＃61;head[x];i;i&＃61;edge[i].nex){int y&＃61;edge[i].to;ll w&＃61;edge[i].len;if(y&＃61;&＃61;fa) continue;if(son[x]&＃61;&＃61;y) dp[y][2]&＃61;max(dp[x][1],dp[x][2])&＃43;w;//y节点是其父最大距离要经过的儿子else dp[y][2]&＃61;max(dp[x][0],dp[x][2])&＃43;w;//y节点不是其父最大距离要经过的儿子dfs2(y,x);}
}
int main(){int n;while(~scanf("%d",&n)){m(head,0),tot&＃61;0;for(int i&＃61;2;i<&＃61;n;&＃43;&＃43;i){int y;ll w;scanf("%d%lld",&y,&w);add(i,y,w);}dfs1(1,1),dfs2(1,1);for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) printf("%d\n",max(dp[i][0],dp[i][2]));}
}