1424 零树（树形DP）

1424 零树

题意

给出一棵树，每次可以选择一个包含节点 1 的连通块，将所有的节点的权值同时加 1 或减 1 ，问最少多少次操作使所有节点权值变为 0 。

分析

这种题意简单的题目好处就是能很快知道自己会不会做，有些很长的英文题搞半天题意还理解错了。

树形DP。首先需要两个数组 d1 d2 分别表示当前节点的正值或负值需要变成 0 。

先考虑都是正值的情况，对于子节点而言只需要找到子节点中最大的正值 max_d1 即可，因为其它小的正值可以在减数的时候顺带全部减掉，如果当前节点 i 的花费 d1[i] > max_d1 那么这个最大的正值也不需要考虑了，同样可以顺带减掉，但是如果 d1[i] < max_d1 时，我们要让 d2[i] += d1[i] - max_d1，同时 d1[i] = max_d1 向上传递，

比如 1(3) -> 2(5)，同时减 5 后，那么节点 2 成功变成 0 了，但是节点 1 会变成 -2 。

负值的情况同理。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

const int INF = 1e9;

ll d1[MAXN], d2[MAXN];

int n;

vector<int> G[MAXN];

void dfs(int pre, int u) {

    ll mn = 0, mx = 0;

    for(int i = 0; i < G[u].size(); i++) {

        int v = G[u][i];

        if(v == pre) continue;

        dfs(u, v);

        mx = max(mx, d1[v]);

        mn = min(mn, d2[v]);

    }

    if(d1[u] < mx) {

        d2[u] += d1[u] - mx;

        d1[u] = mx;

    }

    if(d2[u] > mn) {

        d1[u] += d2[u] - mn;

        d2[u] = mn;

    }

}

int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    cin >> n;

    for(int i = 1; i < n; i++) {

        int a, b;

        cin >> a >> b;

        G[a].push_back(b);

        G[b].push_back(a);

    }

    for(int i = 1; i <= n; i++) {

        ll c;

        cin >> c;

        if(c > 0) {

            d1[i] = c;

        } else {

            d2[i] = c;

        }

    }

    dfs(0, 1);

    cout << d1[1] - d2[1] << endl;

    return 0;

}

巴特西

1424 零树（树形DP）

1424 零树

题意

分析

最新文章

热门文章

巴特西

1424 零树 （树形DP）

1424 零树

题意

分析

最新文章

热门文章

1424 零树（树形DP）