树形dp
本文出自 http://blog.csdn.net/shuangde800
题意：
给出一棵树，求离每个节点最远的点的距离
思路：
把无根树转化成有根树分析，
对于上面那棵树，要求距结点2的最长距离，那么，就需要知道以2为顶点的子树（蓝色圈起的部分，我们叫它Tree（2）），距顶点2的最远距离L1
还有知道2的父节点1为根节点的树Tree（1）-Tree(2)部分（即红色圈起部分），距离结点1的最长距离+dist(1,2) = L2，那么最终距离结点2最远的距离就是max{L1，L2}
f[i][0],表示顶点为i的子树的，距顶点i的最长距离
f[i][1],表示Tree(i的父节点)-Tree(i)的最长距离+i跟i的父节点距离
要求所有的f[i][0]很简单，只要先做一次dfs求每个结点到叶子结点的最长距离即可。
然后要求f[i][1], 可以从父节点递推到子节点，
假设节点u有n个子节点，分别是v1,v2...vn
那么
如果vi不是u最长距离经过的节点，f[vi][1] = dist(vi,u)+max(f[u][0], f[u][1])
如果vi是u最长距离经过的节点，那么不能选择f[u][0],因为这保存的就是最长距离，要选择Tree（u）第二大距离secondDist,
可得f[vi][1] = dist(vi, u) + max(secondDist, f[u][1])
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
#define maxn 10010
#define INF 0x7fffffff
#define inf 10000000
#define MOD 1000000007
#define ull unsigned long long
#define ll long long
using namespace std; struct Node
{
int v, w;
}; vector<Node>adj[maxn]; int indeg[maxn];
int val[maxn];
int n, m;
ll f[maxn][2];
int vis[maxn]; ll dfs1(int u)
{
vis[u] = true;
f[u][0] = 0;
for(int i = 0; i < (int)adj[u].size(); ++ i)
{
int v = adj[u][i].v;
int w = adj[u][i].w;
if(vis[v]) continue;
f[u][0] = max(f[u][0], dfs1(v)+w);
}
return f[u][0];
} void dfs2(int u, int fa_w)
{
vis[u] = true;
int max1 = 0, v1, max2 = 0;
for(int i = 0; i < (int)adj[u].size(); ++ i)
{
int v = adj[u][i].v;
int w = adj[u][i].w;
if(vis[v]) continue;
int tmp = f[v][0] + w;
if(tmp > max1)
{
max2 = max1;
max1 = tmp;
v1 = v;
}
else if(tmp == max1 || tmp>max2)
max2 = tmp;
} if(u != 1)
{
int tmp = f[u][1];
int v = -1;
if(tmp > max1)
{
max2 = max1;
max1 = tmp;
v1 = v;
}
else if(tmp == max1 || tmp>max2)
max2 = tmp;
}
for(int i = 0; i < (int)adj[u].size(); ++ i)
{
int v = adj[u][i].v;
int w = adj[u][i].w;
if(vis[v]) continue;
if(v==v1) f[v][1] = max2 + w;
else f[v][1] = max1 + w;
dfs2(v, w);
}
} int main()
{
while(scanf("%d", &n) == 1 && n)
{
for(int i = 1; i <= n; ++ i) adj[i].clear();
for(int u = 2; u <= n; ++ u)
{
int v, w;
scanf("%d%d", &v, &w);
adj[u].push_back((Node){v, w});
adj[v].push_back((Node){u, w});
}
memset(f, 0, sizeof(f));
memset(vis, 0, sizeof(vis));
dfs1(1);
memset(vis, 0, sizeof(vis));
dfs2(1, 0);
for(int i=1; i<=n; ++i)
printf("%I64d\n", max(f[i][0], f[i][1]));
}
return 0;
}