DSU on Tree

Analysis

DSU on Tree 在一些比较简单的子树问题时可以替代点分治，复杂度也是 \(\mathcal O(n\log n)\) 。

按子树 size 轻重链剖分，然后使用某个数据结构统计每个点的子树信息：

  1. 先让轻儿子统计子树信息，并撤销对数据结构的影响；

  2. 如果有重儿子，统计重儿子子树信息，保留对数据结构的影响（不撤销）；

  3. 向数据结构中添加轻儿子子树信息和当前点信息，统计当前点信息。

复杂度分析：

每个点只会在到根路径上遇到轻边时被添加 /撤销，由轻重连剖分每个点到根的路径上至多 \(\log n\) 条轻边。

所以总复杂度是 \(\mathcal O(n \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
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

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
#define pb push_back

int sz[N], mxs[N];

vector<int> e[N];

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;
        }
}

inline void upd(int u) {
    // adding information of u into data structures
}

inline void del(int u) {
    // deleting information of u from data structures
}

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

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

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

int main() {
    int n = rd();
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd(); 
        e[u].pb(v); e[v].pb(u);
    }
    dfs(1, 1); dsu(1, 1);
    return 0;
}

CF 600 E. Lomsat gelral

一棵树每个点有一个颜色 \(c_i\) ，求每个点子树内出现次数最多的颜色的和。

对颜色维护 cnt 数组，由于 DSU 统计时只有加法，因此可以记录出现最多的次数 mx 和最多次数的颜色的和 res 。

每次 ++cnt[col[u]] 的时候讨论一下和 mx 的关系更新即可（见 upd 函数）。

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

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
#define pb push_back

ll ans[N], res;

int cnt[N], col[N], mx;

int sz[N], mxs[N];

vector<int> e[N];

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;
        }
}

inline void upd(int u) {
    // adding information of u into data structures
    ++cnt[col[u]];
    if (cnt[col[u]] > mx) {mx = cnt[col[u]]; res = col[u];}
    else if (cnt[col[u]] == mx) res += col[u];
}

inline void del(int u) {
    // deleting information of u from data structures
    mx = 0; res = 0; cnt[col[u]] = 0;
}

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

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

void dsu(int u, int fa) {
    for (auto v : e[u])
        if (v != fa && v != mxs[u]) {dsu(v, u); del(v, u);}
    if (mxs[u]) dsu(mxs[u], u);
    for (auto v : e[u])
        if (v != fa && v != mxs[u]) upd(v, u);
    upd(u); ans[u] = res;
}

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) col[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); dsu(1, 1);
    for (int i = 1; i <= n; ++i) printf("%lld ", ans[i]);
    return 0;
}

CF 1009 F. Dominant Indices

给一棵树，对于每一个点求最小的 \(k\) ，使得子树内到他距离为 \(k\) 的点最多。

做法和上一题完全相同，每次更新的时候讨论，超过了 mx 直接覆盖 res ，等于 mx 和 res 取 \(\min\) 。

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;

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 fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define pic       pair<int, char>
#define lowbit(x) ((x) & -(x))

#define N 1000007

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

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

vector<int> e[N];

void dfs(int u, int fa) {
    sz[u] = 1; 
    dep[u] = dep[fa] + 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;
        }
}

inline void upd(int u) {
    // adding information of u into data structures
    ++cnt[dep[u]];
    if (cnt[dep[u]] > mx) {mx = cnt[dep[u]]; res = dep[u];}
    else if (cnt[dep[u]] == mx) res = min(res, dep[u]);
}

inline void del(int u) {
    // deleting information of u from data structures
    mx = 0; res = 0; cnt[dep[u]] = 0;
}

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

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

void dsu(int u, int fa) {
    for (auto v : e[u])
        if (v != fa && v != mxs[u]) {dsu(v, u); del(v, u);}
    if (mxs[u]) dsu(mxs[u], u);
    for (auto v : e[u])
        if (v != fa && v != mxs[u]) upd(v, u);
    upd(u); ans[u] = res - dep[u];
}

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

CF 208 E. Blood Cousins

给一个森林，\(q\) 次问与 \(u_i\) 有共同的第 \(k_i\) 级祖先的点的个数。

询问其实与 \(u_i\) 关系不大，离线后是绑定在 \(u_i\) 的 \(k_i\) 级祖先上的，因此需要快速求 \(k\) 级祖先。

然后使用 DSU 求出 dep 的 cnt 数组即可，由于 DSU 本身也要用到轻重剖分，所以求祖先就也用树剖实现了。

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

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
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>

int tot, dfn[N], seq[N], top[N], dep[N], ans[N], cnt[N], fa[N];

int sz[N], mxs[N];

vector<int> son[N];

vector<pii> que[N];

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

void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++tot;
    seq[tot] = u;
    if (mxs[u]) {dep[mxs[u]] = dep[u] + 1; dfs2(mxs[u], t);}
    for (auto v : son[u]) 
        if (!dfn[v]) {dep[v] = dep[u] + 1; dfs2(v, v);}
}

void upd(int u) {
    ++cnt[dep[u]];
    for (auto v : son[u]) upd(v);
}

void del(int u) {
    --cnt[dep[u]];
    for (auto v : son[u]) del(v);
}

void dsu(int u) {
    for (auto v : son[u]) if (v != mxs[u]) {dsu(v); del(v);}
    if (mxs[u]) dsu(mxs[u]);
    for (auto v : son[u]) if (v != mxs[u]) upd(v);
    ++cnt[dep[u]]; 
    for (auto q : que[u]) ans[q.sc] = cnt[dep[u] + q.fr] - 1;
}

inline int anc(int u, int k) {
    if (dep[u] < k) return 0;
    int nw = u;
    while (dep[u] - dep[top[nw]] < k) nw = fa[top[nw]];
    return seq[dfn[nw] - (k - (dep[u] - dep[nw]))];
}

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) son[fa[i] = rd()].pb(i);        
    for (auto u : son[0]) dfs(u);    
    for (auto u : son[0]) dfs2(u, u); 
    int q = rd();
    for (int i = 1; i <= q; ++i) {
        int u = rd(), k = rd();
        int w = anc(u, k);
        if (w == 0) continue;
        que[w].pb(mp(k, i));
    }
    for (auto u : son[0]) {dsu(u); del(u);}
    for (int i = 1; i <= q; ++i) printf("%d ", ans[i]);
    return 0;
}

另一种比较有意思的做法：

  1. 全部离线，DFS 时用栈记录从根到当前点的路径，得到 \(k\) 级祖先，复杂度 \(\mathcal O(n)\) 。
  2. 将询问按深度分类，先将该深度的点加入数据结构，然后就相当于求 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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

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 fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define pic       pair<int, char>
#define lowbit(x) ((x) & -(x))

#define N 100007

vector<pii> q[N], que[N];

int tot, dfn[N], sz[N], ans[N], stk[N], c[N];

vector<int> son[N], cur[N];

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

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

inline int sum(int l, int r) {
    return sum(r) - sum(l - 1);
}

void dfs(int u, int dep) {
    sz[u] = 1;
    stk[dep] = u; 
    cur[dep].pb(u);
    dfn[u] = ++tot;
    for (auto v : son[u]) {dfs(v, dep + 1); sz[u] += sz[v];}
    for (auto [k, id] : q[u]) 
        if (dep > k) que[dep].pb(mp(stk[dep - k], id));
}

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) son[rd()].pb(i);
    int m = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), k = rd();
        q[u].pb(mp(k, i));
    }
    for (auto u : son[0]) dfs(u, 1);
    for (int i = 1; i <= n; ++i) {
        for (auto u : cur[i]) add(dfn[u], 1);
        for (auto [u, id] : que[i]) 
            ans[id] = sum(dfn[u], dfn[u] + sz[u] - 1) - 1;
        for (auto u : cur[i]) add(dfn[u], -1);
    }
    for (int i = 1; i <= m; ++i) printf("%d ", ans[i]);
    return 0;
}

CF 246 E. Blood Cousins Return

一棵树每个点上有一个字符串，多次询问 \(u_i\) 子树内深度为 \(k\) 的点对应的字符串集合中有多少个不同的。

还是上面那个问题，改成用一个 unordered_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
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 100007
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>

int dfn[N], top[N], dep[N], ans[N], tot, seq[N], fa[N];

int sz[N], mxs[N];

string nam[N];

vector<int> son[N];

vector<pii> que[N];

unordered_map<string, int> cnt[N];

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

void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++tot;
    seq[tot] = u;
    if (mxs[u]) {dep[mxs[u]] = dep[u] + 1; dfs2(mxs[u], t);}
    for (auto v : son[u]) 
        if (!dfn[v]) {dep[v] = dep[u] + 1; dfs2(v, v);}
}

inline void upd(int u) {
    // adding information of u into data structures
    ++cnt[dep[u]][nam[u]];
}

inline void del(int u) {
    // deleting information of u from data structures
    --cnt[dep[u]][nam[u]];
    if (!cnt[dep[u]][nam[u]]) cnt[dep[u]].erase(nam[u]);
}

void upd(int u, int fa) {
    upd(u);
    for (auto v : son[u]) upd(v, u);
}

void del(int u, int fa) {
    del(u);
    for (auto v : son[u]) del(v, u);
}

void dsu(int u, int fa) {
    for (auto v : son[u])
        if (v != mxs[u]) {dsu(v, u); del(v, u);}
    if (mxs[u]) dsu(mxs[u], u);
    for (auto v : son[u])
        if (v != mxs[u]) upd(v, u);
    upd(u); 
    for (auto q : que[u]) {
        int d = q.fr, id = q.sc;
        ans[id] = cnt[dep[u] + d].size();
    }
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> nam[i] >> fa[i];
        son[fa[i]].pb(i);        
    }
    for (auto u : son[0]) dfs(u);    
    for (auto u : son[0]) dfs2(u, u); 
    int q; cin >> q;
    for (int i = 1, u, k; i <= q; ++i) {
        cin >> u >> k;
        if (dep[u] + k > n) continue;
        que[u].pb(mp(k, i));
    }
    for (auto u : son[0]) {dsu(u, u); del(u, u);}
    for (int i = 1; i <= q; ++i) cout << ans[i] << endl;
    return 0;
}

CF 570 D. Tree Requests

一棵树每个点上有一个字符，每次询问 \(u_i\) 子树内深度为 \(k_i\) 的所有点上的字符是否可以通过重排形成回文串。

形成回文串的条件是出现奇数次的字符至多一种。

用 DSU on Tree 维护 cnt[dep][c] 表示在 dep 这个深度上的点字符 c 的出现次数。

再用一个 odd[dep] 表示 cnt[dep][c] 是奇数的 c 的个数，询问 Yes 就是对应深度的 odd[dep] <= 1 。

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

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 fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define pic       pair<int, char>
#define lowbit(x) ((x) & -(x))

#define N 500007

bool ans[N];

int cnt[N][26], ch[N], odd[N];

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

vector<int> son[N];

vector<pii> que[N];

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

inline void upd(int u) {
    // adding information of u into data structures
    ++cnt[dep[u]][ch[u]];
    (cnt[dep[u]][ch[u]] & 1) ? ++odd[dep[u]] : --odd[dep[u]];
}

inline void del(int u) {
    // deleting information of u from data structures
    cnt[dep[u]][ch[u]] = odd[dep[u]] = 0;
}

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

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

void dsu(int u, int fa) {
    for (auto v : son[u])
        if (v != fa && v != mxs[u]) {dsu(v, u); del(v, u);}
    if (mxs[u]) dsu(mxs[u], u);
    for (auto v : son[u])
        if (v != fa && v != mxs[u]) upd(v, u);
    upd(u); 
    for (auto [k, id] : que[u]) ans[id] = (odd[k] <= 1);
}

int main() {
    int n = rd(), m = rd();
    for (int i = 2; i <= n; ++i) son[rd()].pb(i);
    char c = getchar();
    while (!isalpha(c)) c = getchar();
    for (int i = 1; i <= n; ++i, c = getchar()) ch[i] = c - 'a';
    for (int i = 1; i <= m; ++i) {
        int u = rd(), k = rd(); que[u].pb(mp(k, i));
    }
    dfs(1, 1); dsu(1, 1);
    for (int i = 1; i <= m; ++i) puts(ans[i] ? "Yes" : "No");
    return 0;
}

CF 375 D. Tree and Queries

一棵树每个点有一个颜色，每次询问 \(u_i\) 子树内出现次数超过 \(k_i\) 的颜色数。

DSU on Tree 求出来子树内颜色的出现次数 cnt 数组，再对 cnt 求出现次数 cnt' 数组，询问就是问 cnt' 的 \(k_i\) 后缀和。

因此很容易 \(\mathcal O(n\log^2 n)\) 做，额外再用一个树状数组维护 cnt' 就好了。

但实际上可以 \(\mathcal O(n\log n)\) 处理，我们实际在做：1. 对 cnt' 中某个位置 x 执行 --cnt'[x], ++cnt'[x+1]; 2. 求后缀和。

可以发现修改操作对后缀和数组的影响是 \(\mathcal O(1)\) 的，所以我们可以直接在修改的同时维护每个位置的后缀和。

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;

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 fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define pic       pair<int, char>
#define lowbit(x) ((x) & -(x))

#define N 100007

int col[N], cnt[N], sum[N], ans[N];

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

vector<int> e[N];

vector<pii> que[N];

void dfs(int u, int fa) {
    sz[u] = 1; 
    dep[u] = dep[fa] + 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;
        }
}

inline void upd(int u) {
    // adding information of u into data structures
    ++sum[++cnt[col[u]]];
}

inline void del(int u) {
    // deleting information of u from data structures
    sum[cnt[col[u]]--]--;
}

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

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

void dsu(int u, int fa) {
    for (auto v : e[u])
        if (v != fa && v != mxs[u]) {dsu(v, u); del(v, u);}
    if (mxs[u]) dsu(mxs[u], u);
    for (auto v : e[u])
        if (v != fa && v != mxs[u]) upd(v, u);
    upd(u); 
    for (auto [k, id] : que[u]) ans[id] = sum[k];
}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) col[i] = rd();
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd(); e[u].pb(v); e[v].pb(u);   
    }
    for (int i = 1; i <= m; ++i) {
        int u = rd(), k = rd(); que[u].pb(mp(k, i));
    }
    dfs(1, 1); dsu(1, 1);
    for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}

2020 CCPC Changchun F. Strange Memory

给一棵树，每个点有一个权值 \(a_i\) ，求 \(\sum_{1\le i<j\le n} [a_i\oplus a_j=a_{lca(i,j)}] (i\oplus j)\)

直接 dsu on tree 会发现无法处理形如 \(\sum (w_i\oplus x)\) 的查询，因此可以按位统计（注意是节点编号的位数）。

每次将一个子树的答案先查出来再加入，因为 \(a_i>0\) 所以不用考虑祖先后代关系的贡献。

总复杂度 \(\mathcal{O}(n\log^2 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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

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 fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define pic       pair<int, char>
#define lowbit(x) ((x) & -(x))

#define N 1000007

int cnt[N << 1][2], mx, res;

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

ll ans;

vector<int> e[N], subtree[N];

void dfs(int u, int fa) {
    sz[u] = 1; 
    dep[u] = dep[fa] + 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 calc(int u, int fa, int w) {
    for (auto v : e[u]) if (v != fa) calc(v, u, w);
}

void dsu(int u, int fa) {
    for (auto v : e[u])
        if (v != fa && v != mxs[u]) {
            dsu(v, u);
            for (auto k : subtree[v]) cnt[a[k]][(k >> b) & 1] = 0;
        }
    if (mxs[u]) dsu(mxs[u], u);
    for (auto v : e[u])
        if (v != fa && v != mxs[u]) {
            for (auto k : subtree[v]) 
                ans += (1ll << b) * cnt[a[k] ^ a[u]][((k >> b) & 1) ^ 1];
            for (auto k : subtree[v]) ++cnt[a[k]][(k >> b) & 1];
        }
    ++cnt[a[u]][(u >> b) & 1];
}

void get_subtree(int u, int fa, int cur) {
    subtree[cur].pb(u);
    for (auto v : e[u])
        if (v != fa) get_subtree(v, u, cur);
}

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

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) a[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); dsu_tree(1, 1); 
    for (b = 0; b <= 16; ++b) {
        dsu(1, 1); 
        for (int u = 1; u <= n; ++u) cnt[a[u]][0] = cnt[a[u]][1] = 0;
    }
    printf("%lld\n", ans);
    return 0;
}

CF 741 D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

一棵树每条边上有一个字符 (a - v) ，每次询问 \(u_i\) 子树内最长的简单路径，满足其上的字符重排可形成回文串。

\((u,v)\) 路径信息 \(=u\) 到根信息 \(+v\) 到根信息 \(-2*lca(u,v)\) 到根信息。

字符集只有 \(22\) ，状压 \(u\) 到根每个字符的奇偶性 \(s_u\) ，路径信息即为 \(s_u\oplus s_v\) （lca 信息因为异或两次消掉了）

考虑路径合并，每个点可能的配对方案只有 \(23\) 种（异或后为 \(0\) 或 \(2\) 的幂次，即最多允许一个字符出现奇数次）

DSU on Tree，统计此前子树的信息，维护每个状压值的最深深度，保证 lca 是当前点需整个子树先查询后插入。

写挂的地方：1. 子树内最长要和儿子的 ans 取 \(\max\) ；2.枚举配对的状态时，得保证存在再更新。

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;

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 fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define pic       pair<int, char>
#define lowbit(x) ((x) & -(x))

#define N 500007

int ch[N], sta[N], mxd[1 << 22], ans[N], res;

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

vector<int> son[N];

void dfs(int u, int fa, int S) {
    sz[u] = 1; 
    dep[u] = dep[fa] + 1;
    if (u != 1) S ^= (1 << ch[u]);
    sta[u] = S;
    for (auto v : son[u]) {
            dfs(v, u, S); sz[u] += sz[v];
            if (sz[v] > sz[mxs[u]]) mxs[u] = v;
        }
}

inline void upd(int u) {
    // adding information of u into data structures
    mxd[sta[u]] = max(mxd[sta[u]], dep[u]);
}

inline void del(int u) {
    // deleting information of u from data structures
    mxd[sta[u]] = 0; res = 0;
}

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

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

void updans(int u, int del) { 
  	// 枚举配对的状态需要保证存在！！！
    if (mxd[sta[u]]) res = max(res, dep[u] + mxd[sta[u]] - 2 * del);
    for (int i = 0; i < 22; ++i) 
        if (mxd[sta[u] ^ (1 << i)]) res = max(res, dep[u] + mxd[sta[u] ^ (1 << i)] - 2 * del);
}

void getans(int u, int del) {
    updans(u, del);
    for (auto v : son[u]) getans(v, del);
}

void dsu(int u, int fa) {
    for (auto v : son[u])
        if (v != fa && v != mxs[u]) {dsu(v, u); del(v, u);}
    if (mxs[u]) dsu(mxs[u], u);
    updans(u, dep[u]); upd(u); 
    for (auto v : son[u])
        if (v != fa && v != mxs[u]) {
            getans(v, dep[u]); 
            res = max(res, ans[v]);
            upd(v, u);
        }
    ans[u] = res;
}

int main() {
    int n = rd();
    for (int i = 2; i <= n; ++i) {
        son[rd()].pb(i);
        char c = getchar();
        while (!isalpha(c)) c = getchar();
        ch[i] = (c - 'a');
    }
    dfs(1, 1, 0); dsu(1, 1);
    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    return 0;
}

HDU 7255 Expected Inversions

换根 + DSU on Tree 统计信息，见多校题解。

Algorithms
DFS and Similar

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！