【hdu 2196 Computer 】（树形dp求最长路）

链接：https://vjudge.net/contest/204190#problem/C
题意：给一棵树，求树上任意顶点到其他各点的最大值。
分析： 可以容易知道 用树形dp求最长路
首先一次dfs 记录任意顶点到其他各点的最长距离（dp[i][0]）和次长距离（dp[i][1]）。
例子：http://blog.csdn.net/feng_zhiyu/article/details/79182956

然后分析知，一点到其他各点的最长路有两种走法：
1.不经过根 直接到叶子的距离
2.经过根 再到叶子的距离
状态转移方程：
dp【child】【2】 = max（dp【father】【2】，dp【child】【0】+ child.cap==dp【father】【0】？dp【father】【1】：dp【father】【0】）+child.cap；
参考：http://blog.csdn.net/y990041769/article/details/38121945
最后取dp[i][0] 和 dp[i][2] 的较大者

#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <set>
#include <cctype>
#include <cstdlib>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;

#define mem(a,n) memset(a,n,sizeof(a))
#define memc(a,b) memcpy(a,b,sizeof(b))
#define rep(i,a,n) for(int i=a;i<n;i++) ///[a,n)
#define repr(i,n,a) for(int i=n;i>=a;i--)///[n,a]
#define pb push_back
#define fi first
#define se second
#define IO ios::sync_with_stdio(false)
#define fre freopen("in.txt","r",stdin)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef vector<int>vec;
typedef vector<vec>mat;
typedef long long ll;
typedef unsigned long long ull;
const double PI=acos(-1.0);
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const int MOD=1e8;
const int N=1e4+5;
const int dir[4][2]= {-1,0,1,0,0,-1,0,1};
struct Edge
{
    int v,w;
};
int dp[N][3];
int n;
vector<Edge>e[N];
/// dfs 找任意一点到其他点的最长路（dp[i][0]）和次长路（dp[i][1]）并记录
void dfs(int u,int father)///u为当前结点
{
    rep(i,0,e[u].size())
    {
        int v=e[u][i].v;
        int w=e[u][i].w;
        if(v==father) continue;
        dfs(v,u);
        if(dp[v][0]+w>=dp[u][0]) 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;
    }
}
/// dfs 用dp[i][2]记录任意一点经过根节点到其他点的最长路
void dfs2(int u,int father)///u为当前结点
{
    int tmp;
    rep(i,0,e[u].size())
    {
        int v=e[u][i].v;
        int w=e[u][i].w;
        if(v==father) continue;
        if(dp[u][0]==dp[v][0]+w) tmp=dp[u][1];///是从父节点过来的
        else tmp=dp[u][0];///不是
        dp[v][2]=max(dp[u][2],tmp)+w;
        /// 更新从父节点的过来的最大值
        dfs2(v,u);
    }
}
void init()///初始化
{
    mem(dp,0);
    rep(i,0,n+1) e[i].clear();
}
int main()
{
    while(~scanf("%d",&n))
    {
        init();
        rep(i,2,n+1)
        {
            int u=i,v,w;
            scanf("%d%d",&v,&w);
            Edge tmp1=(Edge){v,w};
            e[u].pb(tmp1);
            Edge tmp2=(Edge){u,w};
            e[v].pb(tmp2);
        }
        dfs(1,0);
        dp[1][2]=0;/// 编号1 为根节点
        dfs2(1,0);
        rep(i,1,n+1) printf("%d\n",max(dp[i][0],dp[i][2]));
    }
    return 0;
}