$\large{介绍}$

换根 dp ，相当于对每一个点作为根做一次 dp ，由于父子节点之间换根非常容易，所以可以在 $O(n)$ 的时间内将所有点为根做 dp 。

$\large{例1.Centroids}$

给定一颗树，你有一次将树改造的机会，改造的意思是删去一条边，再加入一条边，保证改造后还是一棵树。

请问有多少点可以通过改造，成为这颗树的重心？（如果以某个点为根，每个子树的大小都不大于 $\lfloor \frac{n}{2} \rfloor$ ，则称某个点为重心）

设 $f_u$ 表示以 $u$ 为根的子树内 $siz$ 小于等于 $\lfloor \frac{n}{2} \rfloor$ 的 $size$ 的最大值

若以 $u$ 为根，$v \in son_u$ ，只需判断 $f_v$ 是否满足 $siz_v - \lfloor \frac{n}{2} \rfloor \leq f_v$ 即可。

使用换根 dp ，时间复杂度 $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;

const int N = 400010;
int n;
int sz[N], mx[N], g[N], vvv[N];
int h[N], e[N * 2], ne[N * 2], idx;
bool ans[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        if (ver == fa) continue;
        dfs(ver, u);
        sz[u] += sz[ver];
        mx[u] = max(mx[u], mx[ver]);
        if (sz[ver] > n / 2) g[u] = ver;
    }
    if (sz[u] <= n / 2) mx[u] = sz[u];
    if ((n - sz[u]) > n / 2) g[u] = fa;
}

void dfs2(int u, int fa) {
    if (!g[u] || sz[g[u]] - n / 2 <= mx[g[u]]) ans[u] = true;
    vector<int> gg;
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        gg.push_back(ver);
        vvv[ver] = gg.size();
    }
    vector<int> pre(gg.size() + 10), suf(gg.size() + 10);
    for (int i = 0; i < gg.size(); i ++ ) pre[i + 1] = max(pre[i], mx[gg[i]]);
    for (int i = gg.size() - 1; i >= 0; i -- ) suf[i + 1] = max(suf[i + 2], mx[gg[i]]);
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        if (ver == fa) continue;
        sz[u] -= sz[ver];
        sz[ver] += sz[u];
        int tmp = mx[u];
        mx[u] = max(pre[vvv[ver] - 1], suf[vvv[ver] + 1]);
        if (sz[u] <= n / 2) mx[u] = sz[u];
        dfs2(ver, u);
        sz[ver] -= sz[u];
        sz[u] += sz[ver];
        mx[u] = tmp;
    }
} 

int main() {
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs(1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
    return 0;
}

$\large{例题2.Kamp}$

维护的东西为当前点与以它为根的所有关键点的最小连通块的边权之和，以及当前点向下走与关键点距离的最大值。

然后再进行换根 dp ，边权值和直接维护，最大值通过维护次大值维护。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 500010;
const ll INF = 1e18;
int n, m;
ll c[N], sum[N], mx[N], ww[N], ans[N];
int v[N], vv[N];
int h[N], e[N * 2], w[N * 2], ne[N * 2], idx;

void add(int a, int b, int cc) {
    e[idx] = b, w[idx] = cc, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int fa) {
    c[u] = v[u];
    mx[u] = v[u] ? 0 : -INF;
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        if (ver == fa) continue;
        dfs(ver, u);
        mx[u] = max(mx[u], mx[ver] + w[i]);
        c[u] += c[ver];
        sum[u] += sum[ver] + (c[ver] ? w[i] : 0);
    }
}

void dfs2(int u, int fa) {
    ans[u] = 2 * sum[u] - mx[u];
    //cout << u << ' ' << sum[u] <<' ' << mx[u] << endl;
    vector<int> gg;
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        gg.push_back(ver);
        vv[ver] = gg.size(), ww[ver] = w[i];
    }
    vector<ll> pre(gg.size() + 10), suf(gg.size() + 10);
    for (int i = 0; i < gg.size(); i ++ ) pre[i + 1] = max(pre[i], mx[gg[i]] + ww[gg[i]]);
    for (int i = gg.size() - 1; i >= 0; i -- ) suf[i + 1] = max(suf[i + 2], mx[gg[i]] + ww[gg[i]]);
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        if (ver != fa) {
            int t1 = mx[u];
            mx[u] = max(pre[vv[ver] - 1], suf[vv[ver] + 1]);
            if (c[u] == c[ver]) mx[u] = -INF;
            int t2 = mx[ver];
            mx[ver] = max(mx[ver], mx[u] + w[i]);
            sum[u] -= sum[ver] + (c[ver] ? w[i] : 0);
            sum[ver] += sum[u] + ((c[u] - c[ver]) ? w[i] : 0);
            c[u] -= c[ver];
            c[ver] += c[u];
            dfs2(ver, u);
            c[ver] -= c[u];
            c[u] += c[ver];
            sum[ver] -= sum[u] + ((c[u] - c[ver]) ? w[i] : 0);
            sum[u] += sum[ver] + (c[ver] ? w[i] : 0);
            mx[u] = t1, mx[ver] = t2;
        }
    }
} 

int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, cc;
        scanf("%d%d%d", &a, &b, &cc);
        add(a, b, cc), add(b, a, cc);
    }
    for (int i = 1; i <= m; i ++ ) {
        int x;
        scanf("%d", &x);
        v[x] = 1;
    }
    dfs(1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; i ++ ) printf("%lld\n", ans[i]);
    return 0;
}

$\large{例题3.连珠线}$

对于每一个点作为根，将它作为第一个加入的点，则蓝线一定分布在 $son-u-fa$ 上。

设 $f_{u,1}$ 表示 $u$ 在某条蓝线的中点上，$f_{u,0}$ 为不在中点上。

$$f_{u,0} = \sum_{v\in son_u} \max \{ f_{ver,1} + w_{u,ver}, f_{ver,0} \}$$

$$f_{u,1} = f_{u,0} + \max_{v\in son_u} \{ f_{ver,0} + w_{u,ver} - \max \{ f_{ver,1} + w_{u,ver}, f_{ver,0} \} \}$$

接下来按照换根dp思路做就行。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 400010;
const ll INF = 1e18;
int n, m;
ll f[N][3], ans;
int h[N], e[N * 2], w[N * 2], ne[N * 2], idx;

void add(int a, int b, int cc) {
    e[idx] = b, w[idx] = cc, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int fa) {
    ll maxn = -INF, maxn2 = -INF;
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        if (ver == fa) continue;
        dfs(ver, u);
        f[u][0] += max(f[ver][0], f[ver][1] + w[i]);
        ll x = f[ver][0] + w[i] - max(f[ver][0], f[ver][1] + w[i]);
        if (x > maxn) maxn2 = maxn, maxn = x;
        else if (x > maxn2) maxn2 = x;
    }
    f[u][1] = f[u][0] + maxn;
    f[u][2] = f[u][0] + maxn2;
}

void dfs2(int u, int fa) {
    ans = max(ans, f[u][0]);
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        if (ver != fa) {
            ll t1 = f[u][0], t2 = f[u][1], t3 = f[u][2], t4 = f[ver][0], t5 = f[ver][1], t6 = f[ver][2];
            f[u][0] -= max(f[ver][0], f[ver][1] + w[i]);
            f[u][1] -= max(f[ver][0], f[ver][1] + w[i]);
            f[u][2] -= max(f[ver][0], f[ver][1] + w[i]);
            if (f[u][1] - f[u][0] == f[ver][0] + w[i] - max(f[ver][0], f[ver][1] + w[i])) f[u][1] = f[u][2];
            f[ver][0] += max(f[u][0], f[u][1] + w[i]);
            f[ver][1] += max(f[u][0], f[u][1] + w[i]);
            f[ver][2] += max(f[u][0], f[u][1] + w[i]);
            ll addv = f[u][0] + w[i] - max(f[u][0], f[u][1] + w[i]);
            if (addv > f[ver][1] - f[ver][0]) f[ver][1] = f[ver][0] + addv;
            else if (addv > f[ver][2] - f[ver][0]) f[ver][2] = f[ver][0] + addv;
            dfs2(ver, u);
            f[u][0] = t1, f[u][1] = t2, f[u][2] = t3, f[ver][0] = t4, f[ver][1] = t5, f[ver][2] = t6;
        }
    }
}

int main() {
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, cc;
        scanf("%d%d%d", &a, &b, &cc);
        add(a, b, cc), add(b, a, cc);
    }
    dfs(1, 0);
    dfs2(1, 0);
    printf("%lld\n", ans);
    return 0;
}