【刷题】【树形dp】computer

题意：给出一个树，求树上每个点可到达的最远距离

思路：搜索两次，一次记录最远距离，一次寻找答案，

用 f[x][0] 表示在 x 的子树下 x 的最远距离，用 f[x][1]  表示在 x 的子树下的次远距离，

用 f[x][2] 表示通过 x 的父亲能走的最远距离，

对于第一次深搜，有 f[x][0]=f[y][0]+dis[i]，

其中 y 是 x 的子树，对于第二次深搜，将 f[y][2] 算出来，最后答案即为 max(f[x][0],f[x][2])

原文链接：https://blog.csdn.net/u011815404/article/details/82960087

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
const int N=10003;
int dis[3][N];//子树中的，最大距离，次大距离 

int tot,head[N];
int ev[N<<1],ew[N<<1],enx[N<<1];
void add(int u,int v,int w)
{
    ev[++tot]=v,ew[tot]=w,enx[tot]=head[u],head[u]=tot;
    ev[++tot]=u,ew[tot]=w,enx[tot]=head[v],head[v]=tot;
}
void dfs1(int rt,int fa)
{
    for(int i=head[rt];i;i=enx[i])
    {
        int nx=ev[i];
        if(nx==fa) continue;

        dfs1(nx,rt);
        if(dis[0][nx]+ew[i]>dis[0][rt])
            dis[1][rt]=dis[0][rt],
            dis[0][rt]=dis[0][nx]+ew[i];
        else if(dis[0][nx]+ew[i]>dis[1][rt])
            dis[1][rt]=dis[0][nx]+ew[i];
    }
}
void dfs2(int rt,int fa)//向上走的最大距离，是整个树，除了自己子树中的最长链，由父亲的父亲，和父亲的另外的儿子（我的兄弟）得来 
{//父亲更新到儿子 
    for(int i=head[rt];i;i=enx[i])
    {
        int nx=ev[i];
        if(nx==fa) continue;

        if(dis[0][rt]==dis[0][nx]+ew[i])
            dis[2][nx]=max(dis[1][rt],dis[2][rt])+ew[i];
        else
            dis[2][nx]=max(dis[0][rt],dis[2][rt])+ew[i];
        dfs2(nx,rt);
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        memset(dis,0,sizeof(dis));
        memset(head,0,sizeof(head));
        tot=0;

        int nx,ww;
        for(int i=2;i<=n;i++)
            scanf("%d%d",&nx,&ww),add(i,nx,ww);

        dfs1(1,0);
        dfs2(1,0);

        for(int i=1;i<=n;i++)
            printf("%d\n",max(dis[0][i],dis[2][i]));
    }
    return 0;
}