简介

换根 DP 是解决当根节点变化时答案也发生变化的问题的题目，通常需要两遍 DFS，一遍先钦定一个点为根处理信息，第二遍是换根 DP。

[POI2008] STA-Station

给定一个 n≤106n\le 10^6 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

题目链接：P3478。

当根节点通过边 (fa,u)(fa,u) 转移时：

  1. 原先 uu 的子树中的任何信息不变。

  2. 现在 fafa 也是 uu 的子结点，所以 fafa 除了 uu 以外的子树所有深度都加一，反映到 sum(u)sum(u) 上就是：

    sum(u)←sum(fa)−[sum(u)+sz(u)]+[n−sz(u)]sum(u)\leftarrow sum(fa)-[sum(u)+sz(u)]+[n-sz(u)]

    第一个中括号里是原本 uu 对 fafa 的贡献。

深度之和，大概是 n2n^2 级别，注意开 long long。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1000010, M = 2000010;
typedef long long LL;
int n, h[N], sz[N], idx = 2;
struct Edge {
    int to, nxt;
} e[M];
LL mx, sum[N];
int mxp;

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

void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = h[u]; i; i = e[i].nxt) {
        int to = e[i].to;
        if (to == fa) continue;
        dfs(to, u);
        sz[u] += sz[to];
        sum[u] += sum[to] + sz[to];
    }
}

void dp(int u, int fa) {
    if (fa) sum[u] += sum[fa] - sum[u] - sz[u] + n - sz[u];
    if (sum[u] > mx) mx = sum[u], mxp = u;
    for (int i = h[u]; i; i = e[i].nxt) {
        int to = e[i].to;
        if (to == fa) continue;
        dp(to, u);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1, a, b; i < n; i++) {
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs(1, 0);
    dp(1, 0);
    return !printf("%d\n", mxp);
}

[ABC160F] Distributing Integers

给定一棵 NN 结点的树，求每个结点作为根时拓扑序的数量。

题目链接：ABC160F。

首先，设 f(u)f(u) 为以 11 为根时 uu 所有子树的拓扑序数量，用 sis_i 表示对应子树的结点数量。

对于 f(u)f(u)，第一个位置一定是给 uu，后面 su−1s_u-1 个位置按顺序分配。

f(u)=(su−1s1)(su−1−s1s2)⋯(snsn)×∏v∈sonuf(v)=(su−1)!(su−1−s1)!s1!×(su−1−s1)!(su−1−s1−s2)!s2!×⋯×1×∏v∈sonuf(v)=(su−1)!∏v∈sonusv!∏v∈sonuf(v)=(su−1)!∏v∈treeusv=n!∏sv\begin{aligned} f(u)&=\binom{s_u-1}{s_1} \binom{s_u-1-s_1}{s_2}\cdots \binom{s_n}{s_n} \times \prod_{v\in son_u} f(v)\\ &=\frac{(s_u-1)!}{(s_u-1-s_1)!s_1!}\times \frac{(s_u-1-s_1)!}{(s_u-1-s_1-s_2)!s_2!}\times \cdots \times 1\times \prod_{v\in son_u}f(v)\\ &=\frac{(s_u-1)!}{\prod_{v\in son_u} s_v!}\prod_{v\in son_u}f(v)\\ &=\frac{(s_u-1)!}{\prod_{v\in tree_u} s_v}\\ &=\frac{n!}{\prod s_v} \end{aligned}

当我们求解根节点的时候，设 dp(u)dp(u) 是以 uu 为根的所有结点的 svs_v 之积，有：

f(u)=n!dp(u),dp(u)=∏v∈Vsvf(u)=\frac{n!}{dp(u)},dp(u)=\prod_{v\in V} s_v

换根时，对于新的根 uu 和原树中 uu 的父结点 fafa，只有它们两个的权值发生了变化：

u:su→nfa:n→n−suu:s_u\to n\\ fa:n\to n-s_u

因此，原本的式子发生的变化是：

(∏v≠u,v≠fasv)sun→(∏v≠u,v≠fasv)n(n−su)(\prod_{v\ne u,v\ne fa} s_v) s_u n\to (\prod_{v\ne u,v\ne fa} s_v) n(n-s_u)

因此 dp(u)dp(u) 应该这样转移：

dp(u)=dp(fa)×n−susudp(u)=dp(fa)\times \frac{n-s_u}{s_u}

所以代码的写法就很显然了。

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
58
59
60
61
62
63
64
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 200010, M = 400010, P = 1e9+7;
int h[N], e[M], ne[M], res[N], n, idx;
LL dp[N], sz[N];

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

LL qmi(LL a, LL k) {
    LL res = 1;
    while (k) {
        if (k & 1) res = res * a % P;
        a = a * a % P;
        k >>= 1;
    }
    return res;
}

void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        sz[u] += sz[j];
    }
    dp[u] = sz[u];
	
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dp[u] = dp[u] * dp[j] % P;
    }
}

void dfs_dp(int u, int fa) {
    if (fa) dp[u] = dp[fa] * (n-sz[u]) % P * qmi(sz[u], P-2) % P;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs_dp(j, u);
    }
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for (int i = 1, a, b; i < n; i++) {
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs(1, 0);
    dfs_dp(1, 0);
    LL fracn = 1;
    for (int i = 2; i <= n; i++) fracn = fracn * i % P;
    for (int i = 1; i <= n; i++) printf("%lld\n", fracn * qmi(dp[i], P-2) % P);
    return 0;
}

[CSP-S2019] 树的重心

对于 nn 个点的树中每条边，求断掉后分裂出的两个子树的重心编号之和，n≤3×105n\le 3\times 10^5。

题目链接：P5666。

重心性质 #1

首先不看这个题，证明一个充要条件：点 uu 是重心 ⇔\Leftrightarrow 删除 uu 后构成的连通块大小的最大值 ≤n/2\le n/2

为了方便理解，我们这里换根为 uu，所以删除 uu 后的所有连通块就是以 uu 的子结点为根的子树。

  1. 充分性：假设 ∃v∈son(u),sz1(v)>n/2\exists v\in son(u),sz_1(v)>n/2，那么以 vv 为根时，sz2(u)≤n/2sz_2(u)\le n/2，此时 uu 一定不是重心。

  2. 必要性：假设 uu 不是重心，满足 ∀v∈son(u),sz1(v)≤n/2\forall v\in son(u),sz_1(v)\le n/2，那么换到 vv 为根时，sz2(u)=n−sz1(v)≥n/2sz_2(u)=n-sz_1(v)\ge n/2。如果 sz1(v)=sz2(u)=n/2sz_1(v)=sz_2(u)=n/2，那么 u,vu,v 都是重心，否则 uu 是重心，因为换到相邻的点不会更优。

    这里 sz1sz_1 指换根前的大小，sz2sz_2 指换根后的大小。

重心性质 #2

一棵树如果存在多个重心，设 uu 是其中一个重心，设存在边 (u,v)(u,v) 那么有：

  1. sz(v)≤n/2sz(v)\le n/2，这是重心的性质。
  2. n−sz(v)≥n/2n-sz(v)\ge n/2，这是不等式的性质。

重心不可能在 vv 的子树中，因为向下走 n−szn-sz 会更大，所以重心只可能是 vv，也就是两个重心之间必然有边，而树上不存在环，所以重心最多只有两个。

当有两个重心时，还需要满足 n−sz(v)≤n/2n-sz(v)\le n/2，于是 sz(v)=n−sz(v)=n/2sz(v)=n-sz(v)=n/2，还需要 nn 为偶数。

重心性质 #3

以 uu 为根时，重心一定在 uu 所在重链上。如果 uu 为重心显然成立，如果不为重心有 sz(son(u))>n/2sz(son(u))>n/2，继续跳，最后一个满足 n−sz(u)≤n/2n-sz(u)\le n/2 的一定是重心，如果有两个那么就是它的父结点。

证明：如果不是重心或者第二重心在下面，那么一定存在重儿子满足 sz(v)≥n/2sz(v)\ge n/2，那么换到 vv 就会有 n−sz(v)≤n/2n-sz(v)\le n/2，这样就和 uu 是最后一个满足条件的矛盾。

所以我们可以用倍增求出这最后一个点。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;

const int N = 300010, M = 600010, K = 19;
int n;
int h[N], sz[N], p[N], f[N][K];
long long res = 0;

int idx = 2;
struct Edge {
    int to, nxt;
} e[M];

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

void calc_res(int u) {
    int n = sz[u];
    for (int k = K-1; k >= 0; k--)
        if (f[u][k] && n - sz[f[u][k]] <= n / 2)
            u = f[u][k];

    res += u;
    if (n % 2 == 0 && sz[u] == n/2) res += p[u];
}

void calc_f(int u, int s) {
    f[u][0] = s;
    for (int k = 1; k < K; k++) f[u][k] = f[f[u][k-1]][k-1];
}

void dfs(int u, int fa) {
    sz[u] = 1, p[u] = fa;
    int s = 0;
    for (int i = h[u]; i; i = e[i].nxt) {
        int to = e[i].to;
        if (to == fa) continue;
        dfs(to, u);
        sz[u] += sz[to];
        if (sz[s] < sz[to]) s = to;
    }
    calc_f(u, s);
}

void dp(int u, int fa) {
    int su = f[u][0], szu = sz[u];

    // dp 的过程中找重儿子和次重儿子比较好
    int s1 = 0, s2 = 0;
    for (int i = h[u]; i; i = e[i].nxt) {
        int to = e[i].to;
        if (sz[to] > sz[s1]) s2 = s1, s1 = to;
        else if (sz[to] > sz[s2]) s2 = to;
    }
    
    for (int i = h[u]; i; i = e[i].nxt) {
        int to = e[i].to;
        if (to == fa) continue;
        calc_res(to);

        if (to == s1) calc_f(u, s2);
        else calc_f(u, s1);

        p[u] = to;
        sz[u] = n - sz[to];

        calc_res(u);

        dp(to, u);
    }

    p[u] = fa, sz[u] = szu;
    calc_f(u, su);
}

void solve() {
    scanf("%d", &n);
    idx = 2;
    for (int i = 1; i <= n; i++) h[i] = 0;

    for (int i = 1, a, b; i < n; i++) {
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    res = 0;
    dfs(1, 0);
    dp(1, 0);

    printf("%lld\n", res);
}

int main() {
    int T;
    scanf("%d", &T);

    while (T--) solve();

    return 0;
}

事实上，你也可以判断重儿子是否 >n/2>n/2​，这样会倍增到最后一个不满足重心要求的点。

但是这样需要特判根为重心的情况，有些麻烦，下面是一个被验证过的正确的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
pair<int, int> calc_res2(int u) {
    int n = sz[u], v = 0;
    if (sz[f[u][0]] <= n / 2) {
        if (n % 2 == 0 && sz[f[u][0]] == n / 2) v = f[u][0];
        return {u, v};
    }

    for (int k = K-1; k >= 0; k--)
        if (f[f[u][k]][0] && sz[f[f[u][k]][0]] > n / 2)
            u = f[u][k];
    u = f[u][0];
    if (n % 2 == 0 && sz[f[u][0]] == n/2) v = f[u][0];
    return {u, v};
}

[CF685B] Kay and Snowflake

给定 nn 个点的树和 qq 次询问，每次询问一个点 uu，求以 uu 为根时重心的标号，若有多个输出任意一个。

题目链接：CF685B。

我不太能理解线性做法，这里先用倍增写一个 O((n+q)log⁡n)O((n+q)\log n) 的在线方法。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 300010, K = 20;
int h[N], sz[N], f[N][K], n, q, idx = 2;
struct Edge {
    int to, nxt;
} e[N];

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

void dfs(int u) {
    sz[u] = 1;

    int s = 0;
    for (int i = h[u]; i; i = e[i].nxt) {
        int to = e[i].to;
        dfs(to);
        sz[u] += sz[to];

        if (sz[s] < sz[to]) s = to;
    }

    f[u][0] = s;
    for (int k = 1; k < K; k++) f[u][k] = f[f[u][k-1]][k-1];
}

int query(int u) {
    int tot = sz[u];
    for (int k = K-1; k >= 0; k--)
        if (tot - sz[f[u][k]] <= tot / 2)
            u = f[u][k];
    return u;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 2, fa; i <= n; i++) {
        scanf("%d", &fa);
        add(fa, i);
    }

    dfs(1);
    for (int i = 1, u; i <= q; i++) {
        scanf("%d", &u);
        printf("%d\n", query(u));
    }

    return 0;
}