HDU - 2196 Computer(树形dp)

Posted on | In , ,

思路

基础树形dp，但看了题解才做出来。。
树形dp有两种基本形式：从根到叶子，从叶子到根。本题稍微有点特别，需要进行两次dfs才能完成整个dp。
我们定义一个dp数组dp[MAXN][3]。dp[i][0]记录的是节点i子树中所有节点到子树根节点i的最大距离，dp[i][1]记录的是节点i往根方向的最大距离，dp[i][2]记录的是节点i子树中所有点的到子树根节点i的次大距离。为什么要这样设计dp状态？如果我们将i节点设为根节点，我们能发现原来父亲节点也变成了一棵子树。但我们不能对每个节点都dfs一次，所以我们考虑使用一个dp[i][1]从顶向下来计算父亲节点这棵子树的距离最大值，dp[i][0],dp[i][2]的作用在后文中会写到。
对于dp[i][0]，dp[i][2]我们在第一次dfs中就计算出来，注意我们要记录一个一个点最长距离走的是哪个儿子longest[i],这个值在后面会用到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int dfs1(int u,int fa){
    dp[u][0]=0;
    for(int i=head[u];~i;i=nxt[i]){
        int go=to[i];
        if(go==fa)continue;
        int temp=dfs1(go,u)+len[i];
        if(temp>dp[u][0]){
            dp[u][2]=dp[u][0];
            dp[u][0]=temp;
            islongest[u]=go;
        }
        else if(temp>dp[u][1]){
            dp[u][1]=temp;
        }
    }
    return dp[u][0];
}

在第二次dfs中我们计算dp[i][1]。我们在父亲节点时计算儿子节点的dp[son][1]而不是dfs进入儿子后计算。然后分类讨论

  1. 对于不是longest的儿子节点，我们显然知道往根方向的最大值是儿子节点到当前节点的距离+当前节点中儿子的最大值和dp[i][1]中的较大值
  2. 是longest的儿子节点，往根方向的最大值是儿子节点到当前节点的距离+dp[i][2]和dp[i][1]中的较大值(注意此时原来所有儿子中的最大值已经不能使用了，因为这个最大值包含在dp[son][0]中，此时只能选择次大值)

最后遍历所有节点取max(dp[i][0],dp[i][1])即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
#define ll long long
#define INF 0x7fffffff
#define inf 0x7fffffffffffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))
#define sqr(x) ((x)*(x))

using namespace std;

const int MAXN=10005,MAXM=MAXN*2;
int head[MAXN],nxt[MAXM],to[MAXM],len[MAXM],edgecnt;
void addedge(int u,int v,int w){
    to[edgecnt]=v;
    len[edgecnt]=w;
    nxt[edgecnt]=head[u];
    head[u]=edgecnt++;
}
int dp[MAXN][3],islongest[MAXN];
int dfs1(int u,int fa){
    dp[u][0]=0;
    for(int i=head[u];~i;i=nxt[i]){
        int go=to[i];
        if(go==fa)continue;
        int temp=dfs1(go,u)+len[i];
        if(temp>dp[u][0]){
            dp[u][2]=dp[u][0];
            dp[u][0]=temp;
            islongest[u]=go;
        }
        else if(temp>dp[u][1]){
            dp[u][1]=temp;
        }
    }
    return dp[u][0];
}
void dfs2(int u,int fa){
    for(int i=head[u];~i;i=nxt[i]){
        int go=to[i];
        if(go==fa)continue;
        if(go==islongest[u]){
            dp[go][1]=len[i]+max(dp[u][2],dp[u][1]);
        }
        else{
            dp[go][1]=len[i]+max(dp[u][0],dp[u][1]);
        }
        dfs2(go,u);
    }
}

int main() {
    int n,u,v;
    while(~scanf("%d",&n)){
        ms(head,-1);
        ms(islongest,-1);
        ms(dp,0);
        edgecnt=0;
        for(int i=2;i<=n;i++){
            scanf("%d%d",&u,&v);
            addedge(i,u,v);
            addedge(u,i,v);
        }
        dfs1(1,-1);
        dfs2(1,-1);
        for(int i=1;i<=n;i++){
            printf("%d\n",max(dp[i][0],dp[i][1]));
        }
    }
    return 0;
}