跃迁引擎启动

Codeforces 741D 题解

发表于 更新于 分类于 阅读次数：

题面

给一棵有根树，每条边有一个 $a$ 到 $v$ 的字母作为权值，询问每个点子树内最长的简单路径，满足经过的边权可以打乱顺序拼成回文串。

分析

一串字母能否变成回文串的条件是最多只能有一个字母出现了奇数次，因此对于一个路径，我们只需要记录上面每个字母出现次数的奇偶性即可。

因为最多只有 $22$ 种字母，因此我们可以把这个状态压成 $bitmasks$，开一个数组记录。

考虑启发式合并，对于每一种状态，我们需要维护的是这种状态出现的最大深度，状态合并时就是二进制异或。

子树信息合并时，只需要询问 $23$ 次对应合法合并状态的最大深度，然后用 $LCA$ 进行差分得到路径长度，更新答案。

代码

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
102
103
104
105
106
107
108
109
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <unordered_map>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1e9 + 7;
const int maxn = 500000 + 50;

vector<PII> edge[maxn];
int n;

int siz[maxn], son[maxn], dep[maxn];
void getsz(int u) {
    siz[u] = 1; int m = -1;
    for (auto& x: edge[u]) {
        int v = x.first;
        dep[v] = dep[u] + 1;
        getsz(v); siz[u] += siz[v];
        if (siz[v] > m) m = siz[v], son[u] = v;
    }
}

int offset, ans[maxn];
int mp[(1 << 22) + 5], tmp[(1 << 22) + 5];
int query(int x) {
    int ans = mp[x ^ offset];
    for (int i = 0; i < 22; i++) {
        ans = max(ans, mp[x ^ (1 << i) ^ offset]);
    }
    return ans;
}
vector<int> vec;
void add(int u, int val, int x) {
    if (x == 1) {
        vec.push_back(val);
        tmp[val] = max(tmp[val], dep[u]);
    } else if (x == 2) {
        tmp[val] = -inf;
    } else {
        mp[val ^ offset] = -inf;
    }
    for (auto& v: edge[u]) {
        add(v.first, val ^ v.second, x);
    }
}
void dfs(int u, int kp) {
    int val = 0;
    for (auto& x: edge[u]) {
        int v = x.first;
        if (v == son[u]) {
            val = x.second; continue;
        }
        dfs(v, 0);
    }
    if (son[u]) {
        // dbg(u, son[u], val);
        dfs(son[u], 1);

        mp[offset] = max(mp[offset], dep[son[u]]);
        offset ^= val;

        ans[u] = max(1, query(0) - dep[u]);
        // dbg(1, u, ans[u]);
        for (auto& x: edge[u]) {
            int v = x.first; 
            if (v == son[u]) continue;
            vec.clear();
            add(v, x.second, 1);
            for (int& info: vec) {
                ans[u] = max(ans[u], query(info) + tmp[info] - 2 * dep[u]);
            }
            for (int& info: vec) {
                mp[info ^ offset] = max(mp[info ^ offset], tmp[info]);
            }
            ans[u] = max(ans[u], query(0) - dep[u]);
            add(v, x.second, 2);
        }
    }
    if (!kp) {
        add(u, 0, -1);
        offset ^= val;
    }
}

void dfs2(int u) {
    for (auto& x: edge[u]) {
        dfs2(x.first); ans[u] = max(ans[u], ans[x.first]);
    }
}

int main() {
    for (int i = 0; i < (1 << 22); i++) tmp[i] = mp[i] = -inf;
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        int x; char ch[2];
        scanf("%d%s", &x, ch); edge[x].push_back({i, 1 << (ch[0] - 'a')});
    } dep[1] = 1; getsz(1);
    dfs(1, 1); dfs2(1);
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    return 0;
}