换根 dp

板子
P2986 [USACO10MAR] Great Cow Gathering G
P3478 [POI2008] STA-Station

P3047 [USACO12FEB] Nearby Cows G
很好的一题
f[i][j] 表示与点 i (向下(点 i 儿子1中的点))距离为 j 的点的权值和
g[i][j] 表示与点 i (所有)距离为 j 的点的权值和
需要特别注意的是刚开始时 g[i][j] = f[i][j] (而不是 g[i][j] = 0)

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

using i64 = long long;

const int N = 1e5 + 100;

int n, k, a[N], f[N][25], g[N][25];
vector<int> G[N];

void dfs1(int x, int fa) {
    f[x][0] = a[x];
    g[x][0] = a[x];
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs1(y, x);
        for (int i = 1; i <= k; i++) {
            f[x][i] += f[y][i - 1];
            g[x][i] += g[y][i - 1];
        }
    }
}

void dfs2(int x, int fa) {
    for (auto y : G[x]) {
        if (y == fa) continue;
        g[y][1] += a[x];
        for (int i = 2; i <= k; i++) {
            g[y][i] += g[x][i - 1] - f[y][i - 2];
        }
        dfs2(y, x);
    }
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dfs1(1, 1); dfs2(1, 1);

    for (int i = 1; i <= n; i++) {
        i64 res = 0;
        for (int j = 0; j <= k; j++) {
            res += g[i][j];
        }
        cout << res << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T = 1; cin >> T;
    // while (T--) solve();
    solve();
    return 0;
}

Maximum White Subtree

也是挺不错的一题
有一个小 trick
设子图中白点个数为 cnt1，黑点个数为 cnt2，请最大化 cnt1 - cnt2
把白点点权视作 1, 黑点点权视作 -1
f[i] 表示点 i 向下能得到的最大权值为多少
g[i] 表示点 i 的答案
当 f[i] < 0
则父亲 fa 一定不会选择点 i 计入答案
g[fa] > 0 g[i] = g[fa] + f[i]
g[fa] < 0 g[i] = f[i];
g[i] = max(g[fa] + f[i], f[i]);
当 f[i] > 0
则父亲 fa 一定会选择点 i 计入答案
g[i] = max(f[i], g[fa]);

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

using i64 = long long;

const int N = 2e5 + 100;

int a[N], f[N], g[N], n;
vector<int> G[N];

void dfs1(int x, int fa) {
    f[x] = a[x];
    g[x] = a[x];
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs1(y, x);
        f[x] += max(0, f[y]);
        g[x] += max(0, g[y]);
    }
}

void dfs2(int x, int fa) {
    for (auto y : G[x]) {
        if (y == fa) continue;
        if (f[y] < 0) g[y] = max(f[y], f[y] + g[x]);
        else g[y] = max(g[x], f[y]); 
        dfs2(y, x);
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (!a[i]) a[i] = -1;
    }

    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs1(1, 1); dfs2(1, 1);

    for (int i = 1; i <= n; i++) {
        cout << g[i] << ' ';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T = 1; cin >> T;
    // while (T--) solve();
    solve();
    return 0;
}

Tree Painting

显然可以观察到的最优策略是从根往下一层一层的染点
那么问题转化为选哪个点作为根最优
换根 dp 一下
g[y] = g[x] + n - 2ll * sz[y];

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

using i64 = long long;

const int N = 2e5 + 100;

int n, sz[N]; 
i64 f[N], g[N];
vector<int> G[N];

void dfs1(int x, int fa) {
    sz[x] = 1;
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs1(y, x);
        sz[x] += sz[y];
        g[x] += g[y];
    }
    g[x] += sz[x];
    f[x] = g[x];
}

void dfs2(int x, int fa) {
    for (auto y : G[x]) {
        if (y == fa) continue;
        g[y] = g[x] + n - 2ll * sz[y];
        dfs2(y, x); 
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs1(1, 1); 
    // for (int i = 1; i <= n; i++) {
    //     cout << i << ' ' << g[i] << endl;
    // }
    dfs2(1, 1);

    cout << *max_element(g + 1, g + 1 + n) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T = 1; cin >> T;
    // while (T--) solve();
    solve();
    return 0;
}

Centroids

很深刻的一题
显然的一件事情是我们指定一个根后要做的事情是 : 消减当前根中子树size最大的那颗子树大小, 使他小于 n / 2
那么问题转化为我们需要维护出以当前点 x 所能得到的最大的 <= n / 2 的子树
采用换根 dp, 一个点有两种子树, 一种是本来他就有的子树, 一种是换根后出去他自己子树后他向上父亲那块子树
第一次 dfs 求出每个点向下能得到的最大的 <= n / 2 的最大的子树是多少, 同时求出每个点 sz 最大和次大的子树是哪两个
第二次求解他向上父亲的子树, 若 n - sz[x] <= n / 2 显然是选择1在外面的整颗子树
若不是, 显然我们需要去在外面的子树中寻找一个最大的 sz 去消减外面那颗子树
这时候就要用到之前维护出来的(同时求出每个点 sz 最大和次大的子树是哪两个)

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

using i64 = long long;

const int N = 4e5 + 100;

int f[N], g[N], sz[N], n;
vector<int> G[N];

int id[N][2];
void dfs1(int x, int fa) {
    sz[x] = 1;
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs1(y, x);
        sz[x] += sz[y];
        f[x] = max(f[x], f[y]);
        if (sz[y] > sz[id[x][0]]) {
            id[x][1] = id[x][0];
            id[x][0] = y;
        } else if (sz[y] > sz[id[x][1]]) {
            id[x][1] = y;
        }
    }
    if (sz[x] <= n / 2) f[x] = sz[x];
}

void dfs2(int x, int fa) {
    for (auto y : G[x]) {
        if (y == fa) continue;
        if (n - sz[y] <= n / 2) g[y] = n - sz[y];
        else if (y != id[x][0]) g[y] = max(g[x], f[id[x][0]]);
        else g[y] = max(g[x], f[id[x][1]]);
        dfs2(y, x);
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs1(1, 1); dfs2(1, 1);

    for (int i = 1; i <= n; i++) {
        if (n - sz[i] > sz[id[i][0]]) cout << (n - sz[i] - g[i] <= n / 2) << ' ';
        else cout << (sz[id[i][0]] - f[id[i][0]] <= n / 2) << ' ';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T = 1; cin >> T;
    // while (T--) solve();
    solve();
    return 0;
}