HDU 2196 Computer（树形DP）

题目链接：

2196 Computer

思路：

1.对于每一个结点$i$，我们需要计算三个值：
$dp[i][0]:$以$i$为根的子树里，$i$往下能达到的最大长度；
$dp[i][1]:$以$i$为根的子树里，$i$往下能达到的次大长度；
$dp[i][2]:$结点$i$往上走，能达到的最长长度；
则$i$能达到的最远距离就是$max(dp[i][0],dp[i][2]))$
其中$dp[i][1]$是为了辅助计算出$dp[i][2]$
2.前两个值我们可以通过一次DFS、从底部往上计算得出；
第三个值我们从上到下用DFS计算；假设现在父结点是$now$、儿子结点是$son$，$now$往下走能达到最远的那一条路可能经过$son$、也可能不经过$son$；
设$cost$为$now$到$son$的花费
如果经过$son$，判断条件是$cost+dp[son.id][0]==dp[now][0]$，此时$son$往上走的最长路径是$max{now$往下、往次长路径走(即$now$需要往下走最长、但不能经过$son$)，$now$往上走$}$；
如果不经过$son$，那就是$max{now$往下、往最长路径走，$now$往上走$}$；

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=1e4+5;
struct node{int id,val;};
vector<node> tree[maxn];
int n,dp[maxn][3];
void dfs1(int now){
    dp[now][0]=dp[now][1]=0;
    for(node& son:tree[now]){
        dfs1(son.id);
        int val=dp[son.id][0]+son.val;
        if(val>=dp[now][0]) dp[now][1]=dp[now][0],dp[now][0]=val;
        else if(val>dp[now][1]) dp[now][1]=val;
    }
}
void dfs2(int now){
    for(node& son:tree[now]){
        if(son.val+dp[son.id][0]==dp[now][0]){
            dp[son.id][2]=max(dp[now][1],dp[now][2])+son.val;
        }else{
            dp[son.id][2]=max(dp[now][0],dp[now][2])+son.val;
        }
        dfs2(son.id);
    }
}
void solve(){
    dfs1(1); dfs2(1);
    for(int i=1;i<=n;i++){
        printf("%d
",max(dp[i][0],dp[i][2]));
        tree[i].clear();
    }
}
int main(){
//    freopen("Sakura.txt","r",stdin);
    while(~scanf("%d",&n)){
        for(int i=2;i<=n;i++){
            int id,val; scanf("%d%d",&id,&val);
            tree[id].push_back(node{i,val});
        }
        solve();
    }
    return 0;
}