Computer （树形DP）

题目链接
题目大意：
给一根无根树，让你求以各个节点为起始点，每个节点到达的最大距离。
输入：输入N表示节点个数，接下来N-1行从2开始，每行输入两个数x1,x2,x1表示第I个节点所连的节点编号，x2表示这条边的权值。
输出：输出每个节点能到达的最大距离。

具体思路：

如图所示计算一个节点所能到达的最大距离包括两部分：
1、以这个节点为根的树所能到达的最大距离，也就是篮圈部分。
2、这个节点父节点为根的树出去蓝色部分所能达到的最大距离+父节点与这个节点相连的边的权值。
这两者取最大值。
所以我们定义
int f[10005][0];表示以x为根节点的和他相连的所有子树的最长距离中的最长值+x根节点到相邻点的距离
int f[10005][1];表示以x为根节点的和他相连的所有子树的最长距离中的次长值+x根节点到相邻点的距离
（不是所有距离中的的次小值）
int f[10005][2];表示通过父节点不经过自身，所能达到的最大距离
f[i][0]和f[i][1]都可以通过一边DFS求出来
注意：

f[i][2]我们需要再DFS一遍，并且分为两种情况分为两种情况：
1、y节点是经过父亲节点f[x][0]的路径上，这时f[y][2]=max(f[x][1]+w, f[x][2]+w)。
2、y节点不经过父亲节点f[x][0]的路径上，这时f[y][2]=max(f[x][0]+w, f[x][2]+w)。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
struct ty{
    int to;
    int weight;
};
vector<ty> g[10005];
int f[10005][3];
int r[10005];
void dfs1(int fa,int x){
    int len=g[x].size();
    for(int i=0;i<len;i++){
        if(g[x][i].to==fa) continue;
        int w=g[x][i].weight;
        dfs1(x,g[x][i].to);
        int temp1=f[g[x][i].to][0];
        //int temp2=f[g[x][i].to][1];
        if(temp1+w>=f[x][0]){
            r[x]=g[x][i].to;
            f[x][1]=f[x][0];
            f[x][0]=temp1+w;
            //if(temp2+w>f[x][1]){（这一步不能要，原因我图片上已经写了）
                //f[x][1]=temp2+w;
            //}
        }
        else if(temp1+w>=f[x][1]){
            f[x][1]=temp1+w;
        }
    }
    return ;
} 
void dfs2(int fa,int x){
    int len=g[x].size();
    for(int i=0;i<len;i++){
        int v=g[x][i].to;
        int w=g[x][i].weight;
        if(v==fa) continue;
        if(r[x]==v){
            f[v][2]=max(f[x][1]+w,f[x][2]+w);
        }
        else{
            f[v][2]=max(f[x][0]+w,f[x][2]+w);
        }
        dfs2(x,v);
    }
    return ;
}
int main(){
    while(~scanf("%d",&n)){
        memset(f,0,sizeof(f));
        memset(r,0,sizeof(r));
        for(int i=0;i<=10001;i++) g[i].clear();
        for(int i=2;i<=n;i++){
        int y,w;
        cin>>y>>w;
        ty a;
        a.to=y;
        a.weight=w;
        g[i].push_back(a);
        a.to=i;
        a.weight=w;
        g[y].push_back(a);
    }
    dfs1(1,1);
    dfs2(1,1);
    for(int i=1;i<=n;i++){
        cout<<max(f[i][0],f[i][2])<<endl;
    }
}
    return 0;
}