CodeForces 274B (Zero Tree)[树型DP]

发表于 | 更新于 | | 阅读次数：

题目链接：http://codeforces.com/problemset/problem/274/B

题目大意：给定一颗以1为根结点的树，每个结点有一个权值，每次选择包含根结点的子树（注意：这里的子树与一般意义的子树定义不同，这里的子树是只要包含根结点的连通树就行，不一定非要包含所有孩子结点）并把这棵子树上的所有结点权值加一或减一，问至少多少次操作能让这棵树权值为零。

这题题意理解了半天。。

可以看到一个结点的孩子结点一定比它先处理完成（否则即使处理完了这个结点，在处理这个结点的孩子结点时，这个结点仍然会受到影响）。这满足无后效性原则，可以考虑树型DP。对于每个结点维护一个up值代表它至少需要被加一多少次，和一个down值代表它至少需要被减一多少次。每次状态转移时分两步：第一步up[u]=max{up[v]}, down[u]=max{down[v]}，第二步合并up[u], down[v], c[u]并将当前结点需要改变的值统计如up[u]或down[u]中。最终的结果就是up[1]+down[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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100009;
typedef long long ll;
int head[maxn];
struct Edge {
    int v,next;
}ed[maxn*2];
int ne=0;
int root=1;
void add(int u,int v) {
    ed[ne].v=v;ed[ne].next=head[u];head[u]=ne++;
}
int c[maxn];
void init() {
    ne=0;
    memset(head,-1,sizeof(head));
}
ll up[maxn],down[maxn];
void dfs(int u,int fa) {
    bool flag=false;
    up[u]=0;
    for(int i=head[u],v;i!=-1;i=ed[i].next) {
        v=ed[i].v;
        if(v==fa) continue;
        flag=true;
        dfs(v,u);
        up[u]=max(up[u],up[v]);
        down[u]=max(down[u],down[v]);
    }
    if(flag) {
        ll tmp=up[u]-down[u]+c[u];
        if(tmp>0) down[u]+=tmp;
        else up[u]+=-tmp;
    }
    else {
        if(c[u]>0) down[u]=c[u];
        else up[u]=-c[u];
    }
}
int main() {
    init();
    int n;
    int u,v;
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        scanf("%d%d",&u,&v);
        add(u,v); add(v,u);
    }
    for(int i=1;i<=n;i++) {
        scanf("%d",c+i);
    }
    dfs(1,0);
    printf("%I64d",up[1]+down[1]);
}