hdoj2196（树形dp，树的直径）

题目链接：https://vjudge.net/problem/HDU-2196

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

思路：

　　如果求得是树上最长距离，两次bfs就行。但这里求的是所有点的最远距离，树形dp的经典题，想了一个小时，还是dp做得太少。分析可得对任意结点u，它的最长距离要么是向下延伸的最长距离，要不向上延伸的最长距离。

　　我们用dp[u][0]表示节点u向下（子结点）的最长距离，pt[u]记录该最长距离经过的第一个子结点编号，比如最长距离经过u->v，那么pt[u]=v。dp[u][1]记录u向下的次短距离，dp[u][0]、dp[u][1]通过一次dfs可以得到，该dfs是由子结点得到父结点的信息。

　　dp[u][2]记录节点u向上（父结点）的最长距离，假设u的父结点为k，分两种情况考虑：

　　　　1.pt[k]=u（k向下的最长路经过u）:dp[u][2]=w_ku+max(dp[k][1],dp[k][2])，即父结点走次长距离，还是向上距离。

　　　　2.pt[k]!=u：dp[u][2]=w_ku+max(dp[k][0],dp[k][2])，即父结点走最长距离，还是向上距离。

　　对每个结点，结果为max(dp[u][0],dp[u][2])。

AC代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn=10005;
struct node{
    int v,w,nex;
}edge[maxn];
int n,dp[maxn][3],pt[maxn],head[maxn],cnt;

void adde(int u,int v,int w){
    edge[++cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nex=head[u];
    head[u]=cnt;
}

void dfs1(int u){
    dp[u][0]=dp[u][1]=pt[u]=0;
    for(int i=head[u];i;i=edge[i].nex){
        int v=edge[i].v,w=edge[i].w;
        dfs1(v);
        if(dp[v][0]+w>=dp[u][0]){
            pt[u]=v;
            dp[u][1]=dp[u][0];
            dp[u][0]=dp[v][0]+w;
        }
        else if(dp[v][0]+w>dp[u][1])
            dp[u][1]=dp[v][0]+w;
    }
}

void dfs2(int u){
    for(int i=head[u];i;i=edge[i].nex){
        int v=edge[i].v,w=edge[i].w;
        if(pt[u]==v) dp[v][2]=w+max(dp[u][1],dp[u][2]);
        else dp[v][2]=w+max(dp[u][0],dp[u][2]);
        dfs2(v);
    }
}

int main(){
    while(~scanf("%d",&n)){
        cnt=0;
        memset(head,0,sizeof(head));
        for(int i=2;i<=n;++i){
            int u,w;
            scanf("%d%d",&u,&w);
            adde(u,i,w);
        }
        dfs1(1);
        dfs2(1);
        for(int i=1;i<=n;++i)
            printf("%d
",max(dp[i][0],dp[i][2]));
    }
    return 0;
}

hdoj2196（树形dp，树的直径）

相关推荐