本文主要是介绍HDU 2196 Computer 树形DP+dfs预处理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：一个有向图，问从每一个点出发可以到达的最远距离。
想法：一个点有出去的边和指向他的边，那么这个点可到达的最远距离要么就是指向他的一条路径，要么就是从他出发的一条路径，我们可以通过dfs搜索点，然后在回溯的过程中找到最长的路径，那么下面就剩下怎么确定只想他的最长的一条路径，如果得到了比较两者大小即可得到正确答案。
现在假设两个点u，v其中u到v有一条边，那么可以知道从u出发的所有路径中会有一个最长的距离，那么这条路径可能会经过v，如果经过v的话，就和v出发的最长路径重合了。显然此时这条路径一定不会是到达v的最长路径，因为这是从v出发的最长路径加上w（u，v），所以如果使这种情况，我们要从u的其他分支中找到除了最长路径以外的次长路径（即是：不通过v的最长路径），那么此时对于u就会面临着和u之前一样的问题，从u出去的边种最大的和到达u的所有路径中最大的。这里再一次dfs，更新dp数组。dp[i]表示所有可以到达i的边中距离最长的。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nodes=10000+5;
const int edges=20000+500;
int n;
struct node
{int v,next,w;
}e[edges];
int head[nodes],cnt,disz[nodes],disc[nodes],dp[nodes],nxt[nodes];
void Init()
{memset(head,-1,sizeof(head));cnt=0;
}
void add(int a,int b,int c)
{e[cnt].v=b;e[cnt].w=c;e[cnt].next=head[a];head[a]=cnt++;
}
int Max(int a,int b)
{if(a>b) return a;return b;
}
void dfs1(int u)
{int z=0,c=0,mark=0;for(int i=head[u];i+1;i=e[i].next){int v=e[i].v;mark=1;dfs1(v);if(z<disz[v]+e[i].w){nxt[u]=v;c=z;z=disz[v]+e[i].w;}else{c=Max(c,disz[v]+e[i].w);}}if(mark){disz[u]=z;disc[u]=c;}else {disz[u]=0;disc[u]=0;}
}
void dfs2(int u)
{for(int i=head[u];i+1;i=e[i].next){int v=e[i].v;if(nxt[u]==v) {dp[v]=Max(dp[u],disc[u])+e[i].w;}else {dp[v]=Max(dp[u],disz[u])+e[i].w;}dfs2(v);}
}
int main()
{while(~scanf("%d",&n)){Init();for(int i=2;i<=n;i++){int a,b;scanf("%d%d",&a,&b);add(a,i,b);}dfs1(1);dp[1]=0;dfs2(1);for(int i=1;i<=n;i++)printf("%d\n",Max(disz[i],dp[i]));}return 0;
}这篇关于HDU 2196 Computer 树形DP+dfs预处理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
