Computer HDU - 2196
Problem Description
A school bought the first computer some time ago(so this computer's id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.
Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4.
Input
Input file contains multiple test cases.In each case there is natural number N (N<=10000) in the first line, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 10^9. Numbers in lines of input are separated by a space.
Output
For each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N).
Sample Input
5
1 1
2 1
3 1
1 1Sample Output
3
2
3
4
4这是一道有点意思的题目，题意是，给你n个电脑，并且电脑之间都相连，要求得每台电脑所等到达的最大距离的电脑。
输入数据是一个n,之后给出n-1行，分别为a和b，第I行表示I到a的权值为b，由于是无向图，在我们读取的时候需要注意以下。
我们把每个电脑看作树的节点，那这样，我们先画一个图
就像这张图一样，我们的题意就是要找距离每个个节点最远的一个距离，因此，对于每个节点(假设为A点)我们有三种情况
第一种是它的通过它子节点的最长路径，这个很好求得，就好像根节点求最长深度类似。
第二个和第三种是通过它的父节点(我们设置为B)的，这时候，我们要求的路径就是通过这个父节点，前往除了A节点的其他路径，因为通过A点的路径就是我们第一种情况，在这个情况之下，我们可以分为走这个父节点B的父节点，或者是走这个父节点B的除了A节点的其他子节点(它的A子节点是第一种情况)。因此，我们需要保存每个节点的深度次短路，方便我们求得通过A节点到其父节点去其他子节点的路径长度，它会等于A到其父亲节点+上这个次短路(最长路是第一种情况了)。
既然知道了我们要求的基本思路，那么我们以一个节点为根，求下每个节点的最深路径，以及最短路径。
通过这两个值，我们可以再去求得它通过其父节点的最长路径。所以我们需要一个数组为dp[3][maxn]。先遍历第一次dfs，我们可以求得dp[0][n]最长路径长度，dp[1][n]次长路径长度，在整个算法中，我们也需要知道，这个节点到哪个节点的路径是最长路径，用一个id[maxn]数组储存。
void dfs1(int root,int pre)
{
for(int i=0;i<G[root].size();i++)
{
node u=G[root][i];
if(u.v==pre)continue;//我们不求通过其父节点的路径
dfs1(u.v,root);
if(dp[0][root]<dp[0][u.v]+u.w)
{
dp[0][root]=dp[0][u.v]+u.w;
id[root]=u.v;//要记录下这个节点通过那个子节点的路径最长
}
}
for(int i=0;i<G[root].size();i++)
{
node u=G[root][i];
if(u.v==pre)continue;
if(id[root]==u.v)continue;//因为通过这个节点是最长路径，所以我们不求
dp[1][root]=max(dp[1][root],dp[0][u.v]+u.w);
}
}我们求得了每个节点的最长路径长度和次长路径长度之后，我们可以去计算通过其父节点的最长路径了，给下代码.....
void dfs2(int root,int pre)
{
for(int i=0;i<G[root].size();i++)
{
node u=G[root][i];
if(pre==u.v)
continue;
if(id[root]==u.v)//表示父节点通过这个节点u.v的路径是包含情况1的，所以我们得选的是次短路径或者父节点 //的父节点
{
dp[2][u.v]=max(dp[2][root],dp[1][root])+u.w;
}else//父节点最长路径没有被情况1包含，所以可以直接走父节点的最长路径或者父节点的父节点{
dp[2][u.v]=max(dp[2][root],dp[0][root])+u.w;
}
dfs2(u.v,root);
}
}放出这道题的全部代码~
#include<iostream>
#include<cstdi
#include<vector>
#include<cstring>
const int maxn = 1e4+5;
using namespace std;
struct node
{
int v,w;
node(int a,int b):v(a),w(b){
}
};
vector<node> G[maxn];
int dp[3][maxn],id[maxn];
void dfs1(int root,int pre)
{
for(int i=0;i<G[root].size();i++)
{
node u=G[root][i];
if(u.v==pre)continue;
dfs1(u.v,root);
if(dp[0][root]<dp[0][u.v]+u.w)
{
dp[0][root]=dp[0][u.v]+u.w;
id[root]=u.v;
}
}
for(int i=0;i<G[root].size();i++)
{
node u=G[root][i];
if(u.v==pre)continue;
if(id[root]==u.v)continue;
dp[1][root]=max(dp[1][root],dp[0][u.v]+u.w);
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
int a,b;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
G[i].clear();
}
for(int i=2;i<=n;i++)
{
scanf("%d%d",&a,&b);
node u=node(a,b);//因为是无向图，所以这个得靠考虑两个方向
node v=node(i,b);
G[i].push_back(u);
G[a].push_back(v);
}
dfs1(1,-1);
dfs2(1,-1);
for(int i=1;i<=n;i++)
{
printf("%d\n", max(dp[0][i], dp[2][i]));//每个节点的最长路径是通过其子节点，或者通过其父节 //点两者的最长路径
}
}
}以上就是这道"入门"树形dp的算法了，一开始思考起来确实比较难理解，但是知道各种路径之间的关系，便可知道这种求法的美妙之处。如果对每个节点都进行dfs暴力的话，它的时间复杂度肯定会很高~