HDU 2196 Computer 经典树形DP
hdu 2196 Computer 经典的树形DP 两次DFS遍历
题意很简单，就是给你一棵树，每条边都有一定的权值，然后让你找到每个点所能走到的最远距离
那么我们可以这样高效的来处理
先以 1 作为根节点进行一次 dfs 遍历，遍历的时候把以 第 i 为根节点往子树方向可以走到的最远距离和次远距离给求出来，且这两个距离是不在同一个分支中的
然后我们进行第二次的从根节点开始dfs遍历，这时候我们要判断的是对于一个节点 i ，除了子树方向上可能有最远距离外，我通过父节点方向是否可以有更加远的距离
，而对于这个操作，我们只要访问父节点所能到达的最远距离，然后接上一段就行了，但是这里会产生一个问题——就是父节点的最远距离可能是会经过当前这个节点
的，因此我们要进行判断当前节点是否在父节点的最远距离的分支上
如果在的话，那么我们要换一个分支，且要是最远的，这个其实就是第一次dfs中求出的与最远路径不在同一分支上的次远路径，我们接上这段进行转移
如果不在的话，那么我们直接接上父节点的最远路径进行转移就行了
代码如下：
#include<iostream>
#include<vector>
using namespace std;
#define N 10001
int n,longest[N],f[N],g[N],dp[N];
//longest[]用来记录当前节点的最远路径所对应的分支编号（因为是邻接表存储的，对于当前节点的判重只要记录下分支编号就行了）
//f[]是当前节点往子树方向所能走过的最远距离，g[]是往子树方向次远距离，dp[]是通过父节点能走过的最远距离
vector<int> son[N],w[N];
int dfs(int root)
{ if(f[root]) return f[root];
int rootsize=son[root].size();
if(!rootsize) return 0; //叶子节点
int est=-1,esti;
int er=-1,eri=-1;
for(int i=0;i<rootsize;i++)
{ if(dfs(son[root][i])+w[root][i]>est)
{ est=f[son[root][i]]+w[root][i];
esti=i;
}
}
longest[root]=esti;
f[root]=est;
for(int i=0;i<rootsize;i++)
{ if(f[son[root][i]]+w[root][i]>er&&i!=esti)
{ er=f[son[root][i]]+w[root][i];
eri=i;
}
}
if(eri!=-1) g[root]=er;
return f[root];
}
void dfs1(int root)
{ int rootsize=son[root].size();
for(int i=0;i<rootsize;i++)
{ if(i==longest[root])
dp[son[root][i]]=max(dp[root],g[root])+w[root][i]; //这里的转移是关键，需要YY一下
else
dp[son[root][i]]=max(dp[root],f[root])+w[root][i];
dfs1(son[root][i]);
}
}
void input()
{ while(scanf("%d",&n)!=EOF)
{ memset(f,0,sizeof(f));
memset(dp,0,sizeof(dp));
memset(g,0,sizeof(g));
memset(longest,-1,sizeof(longest));
for(int i=1;i<=n;i++) son[i].clear(),w[i].clear();
for(int i=2;i<=n;i++)
{ int x1,x2;
scanf("%d%d",&x1,&x2);
son[x1].push_back(i);
w[x1].push_back(x2);
}
f[1]=dfs(1);
dp[1]=0;
dfs1(1);
for(int i=1;i<=n;i++)
printf("%d\n",max(f[i],max(g[i],dp[i])));
}
}
int main()
{ input();
return 0;
}