Yuhang's Blog

树上DP：换根法

2020-12-21 Coding

  1. 1. CF219D
  2. 2. CF543D
  3. 3. CodeForces-708C

更换树根会导致树的某个性质发生改变，而题目需要我们分别求出以每一点为根时，对应的性质的值。

树的性质举例如下：

  • P3478，所有节点深度之和；
  • P2986，所有节点的点权和深度之积的和；
  • P3047，所有深度小于等于$k$的节点点权之和；
  • CF219D，所有由儿子指向父亲的边数。

所谓换根法，是指将问题分为两步：

  1. 先任取一点为根建树，并求出此时的答案；
  2. 不断将当前树根的一个儿子变成树根、当前树根变成这个儿子的儿子（所谓换根），求出这种变化对答案的影响，直到遍历全树。

拿到题目，首先不考虑换根问题，先构造递归状态量$f(u)$（可能视情况要引入其他维度），对每个节点$u$求值后递归得到当前根节点的答案。 而“换根”这一操作可以通过引入cut和link两个互逆的过程来操作：

  • cut(u, v)：当前v是u的儿子，我们把以v为根的子树从以u为根的切断，并统计切断操作对u的答案产生的影响；
  • link(u, v)：将v变成u的儿子，即把以v为根的子树连接到u下面，并统计连接操作对u的答案产生的影响。

而将原先的树根u和它的一个儿子v进行换根，就相当于先进行cut(u, v)，再进行link(v, u)操作。 以上就是换根法的主要精神。 一旦完成了解决问题的第一步，第二步的换根法应当是容易的。原因在于在第一步，我们在递归计算$f(u)$的每一步都在进行link操作，由此可以容易地得到其逆过程cut，进而得到换根操作。 但也有时我们可以通过数学关系直接求出换根操作的递推式，这时cut和link反而可能会比较麻烦。

CF219D

基础的换根操作题。

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,from,to) for(register int i=(int)(from);i<=(int)(to);++i)
#define For(i,to) for(register int i=0;i<(int)(to);++i)
typedef long long ll;
inline ll read(){
    ll x=0; ll sign=1; char c=getchar();
    while(c>'9'  c<'0') {if (c=='-') sign=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*sign;
}
#define N 212345
vector< pair<int, int> > son[N];
int fa[N], f[N], g[N];
int n;

void link(int u, int v, int d) {
    f[u] += f[v];
    f[u] += 1 - d;
}


void cut(int u, int v, int d) {
    f[u] -= f[v];
    f[u] -= 1 - d;
}

void cr(int u, int v, int d) {
    cut(u, v, d);
    link(v, u, 1 - d);
}

void dfsone(int u) {
    for(auto e : son[u]) {
        int v, d; tie(v, d) = e;
        if (v == fa[u]) continue;
        fa[v] = u;
        dfsone(v);
        link(u, v, d);
    }
}

void dfstwo(int u) {
    g[u] = f[u];
    for(auto e : son[u]) {
        int v, d; tie(v, d) = e;
        if (v == fa[u]) continue;
        cr(u, v, d);
        dfstwo(v);
        cr(v, u, 1-d);
    }
}
int main() {
    n = read();
    For(_, n-1) {
        int u = read(), v = read();
        son[u].push_back(make_pair(v, 1));
        son[v].push_back(make_pair(u, 0));
    }
    dfsone(1);
    dfstwo(1);

    int minx = *min_element(g + 1, g + 1 + n);
    printf("%d\n", minx);
    bool first = true;
    rep(i, 1, n) {
        if (g[i] == minx) {
            if (!first) printf(" ");
            if (first) first = false;
            printf("%d", i);
        }
    }
    return 0;
}

CF543D

甚至，在逆运算由于取模意义下乘法等原因的影响下不存在的时候，我们可以定义出可逆运算，如在取模乘法运算中定义0的个数。

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,from,to) for(register int i=(int)(from);i<=(int)(to);++i)
#define For(i,to) for(register int i=0;i<(int)(to);++i)
typedef long long ll;
inline ll read(){
    ll x=0; ll sign=1; char c=getchar();
    while(c>'9'  c<'0') {if (c=='-') sign=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*sign;
}
const ll M = 1000000007ll;
#define N 212345
int n;
vector<int> son[N];
int fa[N];
ll f[N], g[N];
ll zero[N];

ll powm(ll a, ll b, ll p) {
    ll ans = 1;
    a %= p;
    for(; b; b >>= 1) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
    }
    return ans;
}

ll inv(ll a) {
    return powm(a, M - 2, M);
}

void link(int u, int v) {
    if (zero[v]) {
        return;
    }
    if (((1ll + f[v]) % M) == 0) {
        zero[u]++;
        return;
    } 
    f[u] *= (1ll + f[v]);
    f[u] %= M;
}

void cut(int u, int v) {
    if (zero[v]) {
        return;
    }
    if (((1ll + f[v]) % M) == 0) {
        zero[u]--;
        return;
    } 
    f[u] *= inv(1ll + f[v]);
    f[u] %= M;
}

void cr(int u, int v) {
    cut(u, v);
    link(v, u);
}

void dfsone(int u) {
    f[u] = 1ll;
    for(int v : son[u]) if (v != fa[u]) {
        fa[v] = u;
        dfsone(v);
        link(u, v);
    }
}

void dfstwo(int u) {
    g[u] = zero[u] ? 0 : f[u];
    for(int v : son[u]) if (v != fa[u]) {
        cr(u, v);
        dfstwo(v);
        cr(v, u);
    }
}

int main() {

    n = read();
    rep(i, 2, n) {
        int p = read();
        son[i].push_back(p);
        son[p].push_back(i);
    }
    dfsone(1);
    dfstwo(1);
    rep(i, 1, n) {
        cout << (i - 1 ? " " : "") << g[i];
    }
    cout << endl;

    return 0;
}

CodeForces-708C

当我们需要维护的量是儿子中的最大值的时候，我们需要维护次大值来确保去掉一个儿子的贡献的时候可以恢复状态。下面这道题设f1[u]和f2[u]分别是以u的所有儿子为根的子树中，子树大小的最大值和次大值分别在u的哪个儿子中取到；g1[u]和g2[u]分别表示以u为根的子树中，子树大小不超过n/2的最大和次大子树的根节点，但注意最大和次大不同时取在u的一个儿子里面，r1[u]和r2[u]就表示这两个节点是在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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 400100;
int n, fa[N]; vector<int> son[N];
int f1[N], f2[N], g1[N], g2[N], h[N], sz[N];
int r1[N], r2[N];

void update_g(int u, int v, int x) {
    if (sz[x] >= sz[g1[u]]) {
        g2[u] = g1[u];  
        g1[u] = x;      
        r2[u] = r1[u];
        r1[u] = v;
    } else if (sz[x] >= sz[g2[u]]) {
        g2[u] = x;      
        r2[u] = v;
    }
}

void link(int u, int v) {
    sz[u] += sz[v];

    if (sz[v] >= sz[f1[u]]) {
        f2[u] = f1[u];
        f1[u] = v;
    } else if (sz[v] >= sz[f2[u]]) {
        f2[u] = v;
    }

    if (sz[v] <= n/2) {
        update_g(u, v, v);
    } else {
        update_g(u, v, g1[v]);
    }
}

void cut(int u, int v) {
    sz[u] -= sz[v];

    if (v == f1[u]) {
        f1[u] = f2[u];
        f2[u] = 0;
    } else if (v == f2[u]) {
        f2[u] = 0;
    }

    if (v == r1[u]) {
        g1[u] = g2[u];
        g2[u] = 0;
        r1[u] = r2[u];
        r2[u] = 0;
    } else if (v == r2[u]) {
        g2[u] = 0;
        r2[u] = 0;
    }
}

void cr(int u, int v) {
    cut(u, v);
    link(v, u);
}

void dfs1(int u) {
    sz[u] = 1;
    for (int v : son[u]) if (v != fa[u]) {
        fa[v] = u;
        dfs1(v);
        link(u, v);
    }
}

void dfs2(int u) {
    h[u] = (sz[f1[u]] - sz[g1[f1[u]]] <= n/2);
    for (int v : son[u]) if (v != fa[u]) {
        cr(u, v);
        dfs2(v);
        cr(v, u);
    }
}

int main() {
#ifdef D
    freopen("CodeForces-708C.in", "r", stdin);
#endif
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        son[u].push_back(v);
        son[v].push_back(u);
    }
    dfs1(1);
    dfs2(1);
    for (int u = 1; u <= n; u++) {
        printf("%d%c", h[u], u == n ? '\n' : ' ');
    }
    return 0;
}
This article was last updated on days ago, and the information described in the article may have changed.

Published at  , Updated at 

Coding