dsu on tree
Eva.Q Lv9
2022-08-30 16:07:16

“你说过的最勇敢的话是什么？” 男孩问。
“帮帮我。” 马回答。

dsu on tree

用于统计子树信息。

核心与树链剖分相似，为划分轻重儿子；

核心思想：

  1. 先处理轻儿子，并且不保留子树的信息；

  2. 处理重儿子，并保留子树信息；

  3. 再遍历一遍轻儿子，统计答案；

  4. 再加上当前点，统计答案。

时间复杂度分析：

一个点只会被操作 遍历一遍，而被操作 ， 遍历的次数为它到根的链上的轻边个数，最多只有 log 个，所以为 ；

统计每一个子树的众数和

https://codeforces.com/problemset/problem/600/E

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

#define pb push_back

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 100007

vector<int> e[N];

int sz[N], mxs[N], cnt[N], co[N], n, mx; // cnt 统计颜色 mx 全局的众数出现的次数
ll ans[N], res; // res 众数和

void dfs(int u, int fa) {
    sz[u] = 1;
    for (auto v : e[u]) {
        if (v != fa) {
            dfs(v, u); sz[u] += sz[v];
            if (sz[v] > sz[mxs[u]]) mxs[u] = v;
        }
    }
}

void add(int u, int fa) {
    cnt[co[u]]++;
    if (cnt[co[u]] == mx) res += co[u];
    else if (cnt[co[u]] > mx) {res = co[u]; mx = cnt[co[u]];}
    for (auto v : e[u]) {
        if (v != fa) add(v, u);
    }
}

void del(int u, int fa) {
    cnt[co[u]] = 0;
    for (auto v : e[u]) {
        if (v != fa) del(v, u);
    }
}

void dfs1(int u, int fa) {
    for (auto v : e[u]) {
        if (v != fa && v != mxs[u]) {dfs1(v, u); del(v, u); mx = res = 0;}
    }
    if (mxs[u]) dfs1(mxs[u], u);
    for (auto v : e[u])
        if (v != fa && v != mxs[u]) add(v, u);
    cnt[co[u]]++;
    if (cnt[co[u]] == mx) res += co[u];
    else if (cnt[co[u]] > mx) {res = co[u]; mx = cnt[co[u]];}
    ans[u] = res;
}

int main() {
    n = rd();
    for (int i = 1; i <= n; ++i) co[i] = rd();
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd();
        e[u].pb(v); e[v].pb(u);
    }
    dfs(1, 1); dfs1(1, 1);
    for (int i = 1; i <= n; ++i) printf("%lld ", ans[i]);
    return 0;
}

统计一棵树所有可能的 dfs 序的逆序对个数和

https://pintia.cn/problem-sets/994805046380707840/problems/1518582895035215872

用树状数组统计逆序对的个数；将 ”逆序对个数和“ 转换成 ”期望的逆序对个数“ 乘 ”dfs 序“ 的个数。

期望的逆序对个数：对于祖孙关系的逆序对，贡献为 。对于不是祖孙关系的序对，有 的概率成为逆序对。所以期望的逆序对个数就是，祖孙关系逆序对个数 + 不是祖先关系的序对。用 dsu + 树状数组 求祖孙关系逆序对个数。不是祖先关系的序对数 = 全部序对数 - 是祖先关系的序对数。全部序对数 = 。祖先关系的序对数 = 。dfs 序的个数 = 。 

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

#define pb push_back

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 300007
#define mod 1000000007

int c[N], n;

inline int lowbit(int x) {return x & -x;}

inline void add(int p) {
    for (; p <= n; p += lowbit(p)) c[p]++;
}

inline int sum(int p) {
    int tmp = 0;
    for (; p; p -= lowbit(p)) tmp += c[p];
    return tmp;
}

vector<int> e[N];

int sz[N], mxs[N], r;
ll cnt, dfscnt = 1, f[N], res;

void dfs(int u, int fa) {
    sz[u] = 1;
    for (auto v : e[u]) {
        if (v != fa) {
            dfs(v, u); sz[u] += sz[v];
            if (sz[v] > sz[mxs[u]]) mxs[u] = v;
        }
    }
    cnt = (cnt + sz[u] - 1) % mod;
    dfscnt = (1ll * dfscnt * f[e[u].size() - (u != r)]) % mod;
}

void add(int u, int fa) {
    add(u);
    for (auto v : e[u]) {
        if (v != fa) add(v, u);
    }
}

void clear(int p) {
    for (; p <= n; p += lowbit(p)) c[p] = 0;
}

void del(int u, int fa) {
    clear(u);
    for (auto v : e[u]) {
        if (v != fa) del(v, u);
    }
}

void dfs1(int u, int fa) {
    for (auto v : e[u]) {
        if (v != fa && v != mxs[u]) {dfs1(v, u); del(v, u);}
    }
    if (mxs[u]) dfs1(mxs[u], u);
    for (auto v : e[u])
        if (v != fa && v != mxs[u]) add(v, u);
    res = (res + sum(u)) % mod; add(u);
}

inline ll qpow(ll x, int p) {
    ll res = 1;
    for (; p; p >>= 1, x = 1ll * x * x % mod)
        if (p & 1) res = 1ll * res * x % mod;
    return res;
}

int main() {
    n = rd(); r = rd(); f[0] = 1;
    for (int i = 1; i <= n; ++i) f[i] = (1ll * f[i - 1] * i) % mod;
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd();
        e[u].pb(v); e[v].pb(u);
    }
    dfs(r, r); dfs1(r, r);
    printf("%lld\n", ((res + qpow(2, mod - 2) * ((1ll * n * (n - 1) / 2 - cnt) % mod) % mod) * dfscnt) % mod);
    return 0;
}

每个结点上有一个小写字母，每次询问点 的子树中，深度为 的结点上的字母能否构成回文串

https://codeforces.com/problemset/problem/570/D

构成回文串的充要条件是点 的子树中，出现个数为奇数的字母小于等于 个。用数组 cnt[N][26] 统计子树中每个字母出现的次数。由于可能对同一个子树有多次询问（不同深度），对每一个点开一个存放询问的 vector。

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

#define pb push_back

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 500007

vector<int> e[N];
int n;

int sz[N], mxs[N], dep[N];

void dfs1(int u) {
    sz[u] = 1;
    for (auto v : e[u]) {
        dep[v] = dep[u] + 1;
        dfs1(v); sz[u] += sz[v];
        if (sz[v] > sz[mxs[u]]) mxs[u] = v;
    }
}

struct que {int k, id;};

vector<que> q[N];

int cnt[N][27];
bool ans[N];

string s;

void add(int u) {
    cnt[dep[u]][s[u - 1] - 'a']++;
    for (auto v : e[u]) add(v);
}

void del(int u) {
    cnt[dep[u]][s[u - 1] - 'a']--;
    for (auto v : e[u]) del(v);
}

void dfs2(int u) {
    for (auto v : e[u]) {
        if (v != mxs[u]) {dfs2(v); del(v);}
    }
    if (mxs[u]) dfs2(mxs[u]);
    for (auto v : e[u])
        if (v != mxs[u]) add(v);
     cnt[dep[u]][s[u - 1] - 'a']++;
     for (auto cur : q[u]) {
         int tmp = 0;
         for (int i = 0; i < 26; ++i)
            if (cnt[cur.k][i] % 2 == 1) tmp++;
         if (tmp <= 1) ans[cur.id] = 1;
     }
}

int main() {
    n = rd(); int m = rd();
    for (int i = 2; i <= n; ++i) {
        int u = rd(); e[u].pb(i);
    }
    cin >> s;
    for (int i = 1 ; i <= m; ++i) {
        int u = rd(), k = rd();
        q[u].pb(que{k, i});
    }
    dep[1] = 1; dfs1(1); dfs2(1);
    for (int i = 1; i <= m; ++i) puts(ans[i] ? "Yes" : "No");
    return 0;
}

每次询问查询与点 有共同的 级祖先的点的个数 （不包括 ）

https://codeforces.com/problemset/problem/208/E

用倍增思想处理 级祖先；cnt 数组统计各个深度的点数。

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

#define pb push_back

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 100007

vector<int> e[N];
int n, fa[N][21], t, dep[N];

void dfs(int u) {
    for (int i = 1; i <= t; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto v : e[u]) {
        fa[v][0] = u;
        dep[v] = dep[u] + 1;
        dfs(v);
    }
}

int sz[N], mxs[N];

void dfs1(int u) {
    sz[u] = 1;
    for (auto v : e[u]) {
        dfs1(v); sz[u] += sz[v];
        if (sz[v] > sz[mxs[u]]) mxs[u] = v;
    }
}

struct que {int k, u, id;};

vector<que> q[N];

int cnt[N], ans[N];

void add(int u, int fa) {
    cnt[dep[u]]++;
    for (auto v : e[u])
        if (v != fa) add(v, u);
}

void del(int u, int fa) {
    cnt[dep[u]]--;
    for (auto v : e[u])
        if (v != fa) del(v, u);
}

void dfs2(int u) {
    for (auto v : e[u]) {
        if (v != mxs[u]) {dfs2(v); del(v, u);}
    }
    if (mxs[u]) dfs2(mxs[u]);
    for (auto v : e[u])
        if (v != mxs[u]) add(v, u);
     for (auto cur : q[u])
         ans[cur.id] = cnt[dep[u] + cur.k] - 1;
     cnt[dep[u]]++;
}

int main() {
    n = rd(); t = __lg(n);
    for (int i = 1; i <= n; ++i) {
        fa[i + 1][0] = rd() + 1; e[fa[i + 1][0]].pb(i + 1);
    }
    fa[1][0] = 1; dfs(1);
    for (int i = 1; i <= t; ++i)
       for (int j = 1; j <= n + 1; ++j) {
           fa[j][i] = fa[fa[j][i - 1]][i - 1];
       }
    int m = rd();
    for (int i = 1 ; i <= m; ++i) {
        int v = rd() + 1, k = rd();
        if (dep[v] <= k) continue;
        int u = v;
        for (int j = t; j >= 0; --j)
               if (k & (1 << j)) u = fa[u][j];
        q[u].pb(que{k, u, i});
    }
    dfs1(1); dfs2(1);
    for (int i = 1; i <= m; ++i) printf("%d ", ans[i]);
    return 0;
}

每个点上有一个字符串，每次询问查询以点 的 级祖先为根的子树中，与 深度相同深度的点中，有多少个不同的字符串

https://codeforces.com/problemset/problem/246/E

用倍增思想求 级祖先；把询问挂在 级祖先上；用 map 统计有多少个不同的字符串，不用 set 是因为 del 的时候，不应该直接把这个字符串擦掉，因为有可能有别的点上也是这个字符串，所以用 map 当做一个计数器，如果计数器为 了，再把这个字符串删掉。为了防止保证访问不越界，查询时要注意。

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

#define pb push_back

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 100007

vector<int> e[N];
int n;

int sz[N], mxs[N], dep[N];

void dfs1(int u) {
    sz[u] = 1;
    for (auto v : e[u]) {
        dep[v] = dep[u] + 1;
        dfs1(v); sz[u] += sz[v];
        if (sz[v] > sz[mxs[u]]) mxs[u] = v;
    }
}

struct que {int k, id;};

vector<que> q[N];

int cnt[N][27], ans[N];

char name[N][21];
map<string, int> S[N];

void add(int u) {
    S[dep[u]][name[u]]++;
    for (auto v : e[u]) add(v);
}

void del(int u) {
    S[dep[u]][name[u]]--;
    if (S[dep[u]][name[u]] == 0) S[dep[u]].erase(name[u]);
    for (auto v : e[u]) del(v);
}

void dfs2(int u) {
    for (auto v : e[u]) {
        if (v != mxs[u]) {dfs2(v); del(v);}
    }
    if (mxs[u]) dfs2(mxs[u]);
    for (auto v : e[u])
        if (v != mxs[u]) add(v);
     S[dep[u]][name[u]]++;
     for (auto cur : q[u]) {
         if (dep[u] + cur.k > n) continue;
         ans[cur.id] = S[dep[u] + cur.k].size();
     }
}

int main() {
    n = rd();
    for (int i = 1; i <= n; ++i) {
        cin >> name[i];
        int u = rd(); if (u) e[u].pb(i);
    }
    int m = rd();
    for (int i = 1 ; i <= m; ++i) {
        int u = rd(), k = rd();
        q[u].pb(que{k, i});
    }
    for (int i = 1; i <= n; ++i)
        if (!dep[i]) {
            dep[i] = 1; dfs1(i); dfs2(i); del(i);
        }
    for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}

对于每个点，求一个最小的 ，使得 最大。 为 子树中到 距离为 的节点数。

https://codeforces.com/problemset/problem/1009/F

记录子树每个深度的节点的个数，然后取个最大节点个数的最小深度即可

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

#define pb push_back

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 1000007

vector<int> e[N];
int n;

int sz[N], mxs[N], dep[N];

void dfs1(int u, int fa) {
    sz[u] = 1;
    for (auto v : e[u]) {
        if (v != fa) {
            dep[v] = dep[u] + 1;
            dfs1(v, u); sz[u] += sz[v];
            if (sz[v] > sz[mxs[u]]) mxs[u] = v;
        }
    }
}

int cnt[N], ans[N], mx, mxid;

void add(int u, int fa) {
    cnt[dep[u]]++;
    if (cnt[dep[u]] > mx) {mxid = dep[u]; mx = cnt[dep[u]];}
    else if (cnt[dep[u]] == mx) mxid = min(mxid, dep[u]);
    for (auto v : e[u])
        if (v != fa) add(v, u);
}

void del(int u, int fa) {
    cnt[dep[u]]--;
    for (auto v : e[u])
        if (v != fa) del(v, u);
}

void dfs2(int u, int fa) {
    for (auto v : e[u]) {
        if (v != fa && v != mxs[u]) {dfs2(v, u); del(v, u); mx = mxid = 0;}
    }
    if (mxs[u]) dfs2(mxs[u], u);
    for (auto v : e[u])
        if (v != fa && v != mxs[u]) add(v, u);
     cnt[dep[u]]++;
     if (cnt[dep[u]] > mx) {mxid = dep[u]; mx = cnt[dep[u]];}
     else if (cnt[dep[u]] == mx) mxid = min(mxid, dep[u]);
     ans[u] = mxid - dep[u];
}

int main() {
    n = rd();
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd();
        e[u].pb(v); e[v].pb(u);
    }
    dep[1] = 1; dfs1(1, 1); dfs2(1, 1);
    for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    return 0;
}
  • Post title：dsu on tree
  • Post author：Eva.Q
  • Create time：2022-08-30 16:07:16
  • Post link：https://qyy/2022/08/30/Algorithm/dsu-on-tree/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.