Codeforces Round #627 (Div. 3) F. Maximum White Subtree 树形DP 换根

太过爱你忘了你带给我的痛 2023-07-15 13:03 29阅读 0赞

题目链接：[http://codeforces.com/contest/1324/problem/F][http_codeforces.com_contest_1324_problem_F]

题意：给你一颗树，每个结点为白色或者黑色，对于每个子树的权值就是白色点的数量 - 黑色点的数量，求1~n以每个点为根

的子树的权值。

思路：比较裸的换根DP，首先dfs一遍求出来以1为根的代价，然后再考虑每个点换根的代价就行了。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define fi first
    #define se second
    #define ls rt << 1
    #define rs rt << 1|1
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    #define pll pair<ll, ll>
    #define pii pair<int, int>
    #define ull unsigned long long
    #define pdd pair<double, double>
    const int mod = 1e9 + 7;
    const int maxn = 2e5 + 10;
    const int inf = 0x3f3f3f3f;
    int a[maxn], ans[maxn], f[maxn];
    vector<int> e[maxn];
    
    void dfs(int u, int fa)
    {
        f[u] = a[u];
        for(auto v : e[u])
        {
            if(v == fa) continue;
            dfs(v, u);
            f[u] += max(0, f[v]);
        }
    }
    void dfs2(int u, int fa)
    {
        for(auto v : e[u]) //哪个儿子当根
        {
            if(v == fa) continue;
            f[v] += max(0, f[u] - max(0, f[v]));
            dfs2(v, u);
        }
    }
    int main()
    {
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
            if(!a[i]) a[i] = -1;
        }
        for(int i = 1; i < n; ++i)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        dfs(1, 0);
        //for(int i = 1; i <= n; ++i) printf("%d\n", f[i]);
        dfs2(1, 0);
        for(int i = 1; i <= n; ++i) printf("%d ", f[i]);
        return 0;
    }

[http_codeforces.com_contest_1324_problem_F]: http://codeforces.com/contest/1324/problem/F