介绍

树上启发式合并 一般用于 满足以下条件的问题：

  1. 所有询问离线，无修改，仅询问子树的信息（不能用于链的询问）
  2. $ans[u]$ 可以转化为 $\sum\limits_{v}ans[v]$ 的形式（其中，$v$ 是 $u$ 的child）
  3. 如果已知 $ans[v]$，可以在 $O(1)$ 的时间（或者无需任何操作）添加到 $ans[u]$ (其中，$v$ 是 $u$ 的child）

先用 CF600E 来举个例子。

题意

已知一棵包含 $N$ 个节点的有根树（root为 $1$），每个节点 $i$ 有一个颜色 $c_i$。

对于每一个节点 $i$，我们都要求出它的 subtree（包含自己）中，出现颜色次数最多的所有颜色编号和（可能不止一种颜色）。

例：$1$ 的subtree中，共有 5 个节点，颜色分别为 $2,2,5,5,1$，那么出现颜色次数最多的颜色编号为 $2,5$，所求的和为 $2+5 = 7$，所以 $ans_1 = 7$。

输出对于每一个 $i$ 的 $ans_i$

其中，$1\leq n \leq 10^5, 1 \leq c_i \leq n$

思想

暴力做法

首先，我们开一个全局的数组 cnt[]，记录每一种颜色出现的次数。再开一个全局数组 sum[]，其中 sum[i] 代表出现次数为 i 的颜色的编号和。

然后，对于每一个节点 $i$，遍历它 subtree 中的所有节点，统计答案。统计完以后，清空这两个全局数组，再换下一个节点重复此步骤。

复杂度：$O(n^2)$

优化思路

• 注：以下 $u$ 均表示parent，$v$ 表示 $u$ 的child。

我们发现，对于任何一个节点 $u$ ，$cnt[u] = \sum\limits_v cnt[v]$ ，$sum[u] = \sum\limits_v sum[v]$ （这里不是指真的sum，而是说我们可以通过所有child的信息合并，得到 $u$ 的信息）。

那么，我们的暴力思路是：

来到节点 $u$ 时，

  1. 先统计所有 $v$ 的答案 $ans_v$（代表 $v$ 对应subtree的答案），每统计完一个 $v$ 就清空一次全局数组。
  2. 全部的 $v$ 统计完以后，再遍历所有的 $v$ 的subtree，把所有 $v$ 的 cnt[], sum[] 进行合并。
  3. 加上 $u$ 本身，就得到了 $u$ 所在subtree的答案 $ans_u$。

这里我们发现了一个可以优化的地方：

对于最后一个 $v$，我们统计完它以后，不需要清空全局数组，因为我们马上就要进行 Step 2，刚好需要合并所有 $v$ 的信息，所以保留它就可以节省一些时间。

那么这最后一个 $v$，所对应的subtree 自然是 size 越大越好。所以我们就选择 $u$ 的重儿子作为最后一个 $v$。

这就是树上启发式合并了，复杂度为 $O(n\log n)$，证明见下面。

算法步骤

  1. 创建全局数组（一般是 cnt[] 一类的数颜色数组）。
  2. 进行第一次 $DFS$（$dfs_1$），获得每个节点的 sz[]（subtree大小），son[]（重儿子）。
  3. 进行第二次 $DFS$（$dfs_2$），来到节点 $u$ 后：
    1. 先递归 $DFS(v)$，对于每一个 $v$（除了重儿子以外），获得 $ans_v$。然后清空全局数组。
    2. 递归 $DFS(x)$，获得 $ans_x$（其中，$x$ 是 $u$ 的重儿子）。不清空全局数组。
    3. 遍历所有 $v$ 的subtree（除了重儿子以外），把信息加到全局数组上。（注意，这里的遍历并不是上面的 $DFS(v)$，一般实现过程中，用 add(v, 1) 来表示）。
    4. 加上 $u$ 自己的信息，得到 $ans_u$。

模版

vector<int> adj[maxn];

int sz[maxn], son[maxn], par[maxn];
void dfs1(int u, int p) {
    par[u] = p;
    sz[u] = 1;
    int maxsz = -1;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > maxsz) {
            maxsz = sz[v];
            son[u] = v;
        }
    }
}
 
int cnt[maxn], a[maxn];  // 根据题目而定
// 单点更新
void update(int u, int f) {
    int c = a[u];
    cnt[c] += f;
    if (f == 1) {
        if (cnt[c] == 2) mx.insert(c);
    } else {
        if (cnt[c] == 1) mx.erase(c);
    }
}
 
// 遍历subtree，加到数组上。f = 1（加上信息）或者 -1（清空信息）
void add(int u, int p, int f) {  // f = 1: add, f = -1: del
    update(u, f);  // 单点更新
    for (int v : adj[u]) {
        if (v == p) continue;
        add(v, u, f);
    }
}
 
int ans1[maxn], ans2[maxn];
// keep 代表该节点是否为重儿子（如果keep = 1就不清空数组）
// f 代表这个子树对应的是 +1 (加上) 还是 -1 (减去)
void dfs2(int u, int p, bool keep, int f) {
    for (int v : adj[u]) {
        if (v == p || v == son[u]) continue;
        dfs2(v, u, 0, f);  // Step1: 轻儿子不保留信息，keep = 0表示，在dfs2(v)结束后，全局数组不会有任何变化
    }
    if (son[u]) dfs2(son[u], u, 1, f);  // Step2: 重儿子保留信息
    for (int v : adj[u]) {
        if (v == p || v == son[u]) continue;
        add(v, u, f);  // Step3: 遍历所有v（除了重儿子以外），加上信息
    }
    update(u, f);   // Step 4: 单点更新 u 的信息
    if (f == 1) {
        if (mx.size()) ans1[u] = *mx.begin();  // Step4: 得到 ans[u]
    } else {
        if (mx.size()) ans2[u] = *mx.begin();
    }
 
    if (!keep) add(u, p, -f);   // 如果keep = 0，说明需要清空数组，就把整个subtree(u)的影响再减掉就可以了
}
 
int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    dfs1(1, 0);
    dfs2(1, 0, 0, 1);
}

复杂度证明

对于任何一个节点 $u$，如果它被清空了，那么这说明它的某个祖先是轻儿子。而轻儿子的数量 = 重链数量 = $O(\log n)$，所以每个节点最多被清空 $\log n$ 次。总复杂度为 $O(n\log n)$

例题

例1 CF600E

题意和题解都讲了，就直接放代码了：

代码 
using namespace std;
#include <bits/stdc++.h>
 
const int maxn = 1e5+5;
const int maxm = 2e5+5;

int n, sz[maxn], head[maxn], ecnt = 1, color[maxn], son[maxn];
ll cnt[maxn], sum[maxn], ans[maxn], maxcnt = 0;

struct Edge {
    int to, nxt;
} edges[maxm];
void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

void dfs(int u, int p) {
    sz[u] = 1;
    int maxsz = -1;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        dfs(to, u);
        sz[u] += sz[to];
        if (sz[to] > maxsz) {
            maxsz = sz[to];
            son[u] = to;
        }
    }
}

void update(int u, int f) {  // 单点更新
    int c = color[u];
    cnt[c] += (ll)f;
    sum[cnt[c]-f] -= (ll)c;
    sum[cnt[c]] += (ll)c;

    while (f > 0 && sum[maxcnt+1]) maxcnt++;
    if (f < 0) maxcnt = 0;
}

void add(int u, int p, int f) {  // f = 1: add, f = -1: del
    update(u, f);
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        add(to, u, f);
    }
}

void dfs2(int u, int p, bool keep) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p || to == son[u]) continue;
        dfs2(to, u, 0);
    }

    if (son[u]) dfs2(son[u], u, 1);

    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p || to == son[u]) continue;
        add(to, u, 1);
    }

    update(u, 1);
    ans[u] = sum[maxcnt];

    if (!keep) add(u, p, -1);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> color[i];
    for (int i = 1; i <= n-1; i++) {
        int u,v; cin >> u >> v;
        addEdge(u,v); addEdge(v,u);
    }

    dfs(1,0);
    dfs2(1, 0, 1);

    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << endl;
}

例2 CF208E

题意

已知一棵包含 $N$ 个节点的森林（可能有多个root），并且给出 $M$ 个询问。

$v, p$：输出存在多少个点 $u$，使得 $u$ 和 $v$ 的第 $p$ 个祖先相同。

其中，$1\leq n,m \leq 10^5$

法一树上莫队

每次询问 $v,p$ 时，我们先用倍增求出 $v$ 的第 $p$ 个祖先 $x$。那么，问题转化为：

在 $x$ 的 subtree中，有多少个 $u$，使得 dep[u] = dep[x] + p？

那么，用 DFS序 先把树上问题转化为区间问题，就变成了：

在区间 $[L,R]$ 内，有多少个 $u \in [L,R]$ 使得 dep[u] = dep[x] + p ？

然后用 莫队 来处理每个询问即可。

树上莫队代码 
using namespace std;
#include <bits/stdc++.h>

const int mod = 1e9+7;
const int maxn = 1e5+5;
const int maxm = 2e5+5;

int dep[maxn], sz[maxn], head[maxn], ecnt = 1, ans[maxn], n, m, tmp[maxn];
int par[maxn][22];
int cnt[maxn], id[maxn], idcnt = 1;
struct Edge {
    int to, nxt;
} edges[maxm];

struct Query {
    int l,r,id,d;
} q[maxn];

void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

void dfs(int u) {
    sz[u] = 1;
    id[u] = idcnt++;
    dep[u] = dep[par[u][0]] + 1;
    for (int j = 1; j < 22; j++) {  // 注意这里先处理parent，之后再 dfs(to)
        par[u][j] = par[par[u][j-1]][j-1];
    }

    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        dfs(to);
        sz[u] += sz[to];
    }
}

int jump(int u, int p) {
    for (int j = 0; (1<<j) <= p; j++) {
        if ((1<<j) & p)
            u = par[u][j];
    }
    return u;
}

void add(int x) {
    cnt[dep[x]]++;
}

void del(int x) {
    cnt[dep[x]]--;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int u; cin >> u;
        if (u) {
            addEdge(u, i);
            par[i][0] = u;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!par[i][0]) dfs(i);
    }

    memcpy(tmp, dep, sizeof(dep));
    for (int i = 1; i <= n; i++) dep[id[i]] = tmp[i];

    cin >> m;
    for (int i = 1; i <= m; i++) {
        int u,p; cin >> u >> p;
        p = jump(u, p);
        int l,r,d;
        if (!p) l = 0;
        else l = id[p];
        r = l + sz[p] - 1;
        d = dep[id[u]];  // find number of vertices in subtree of u, which has depth d
        q[i] = {l,r,i,d};
    }
    int BLOCK = sqrt(n);
    sort(q+1, q+m+1, [&](auto a, auto b) {
        int be1 = (a.l-1) / BLOCK, be2 = (b.l-1) / BLOCK;
        if (be1 == be2) return a.r < b.r;
        return be1 < be2;
    });

    int l = 1, r = 0;
    for (int i = 1; i <= m; i++) {
        int L,R,ID,D;
        L = q[i].l, R = q[i].r, ID = q[i].id, D = q[i].d;
        if (!L) {
            ans[ID] = 0;
            continue;
        }
        while (r < R) add(++r);
        while (r > R) del(r--);
        while (l > L) add(--l);
        while (l < L) del(l++);
        ans[ID] = cnt[D] - 1;
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << " ";
    cout << endl;
}
法二树上启发式合并

每次询问 $v,p$ 时，我们先用倍增求出 $v$ 的第 $p$ 个祖先 $x$。那么，问题转化为：

在 $x$ 的 subtree中，有多少个 $u$，使得 dep[u] = dep[x] + p？

可以发现，如果我们求出来了 child $v$ 的 cnt[] 信息（即，在 $v$ 的subtree内，每个 dep 对应的节点数量），则直接把 cnt[] 数组加到 parent $u$ 上即可。所以在继承重儿子 cnt[] 信息时，无需任何操作。

这样就可以 树上启发式合并了！

树上启发式合并代码 
using namespace std;
#include <bits/stdc++.h>

const int maxn = 1e5+5;
const int maxm = 2e5+5;
 
int dep[maxn], sz[maxn], head[maxn], ecnt = 1, ans[maxn], n, m, son[maxn];
int par[maxn][22];
int cnt[maxn];
struct Edge {
    int to, nxt;
} edges[maxm];
 
struct Query {
    int id, d;
};
vector<Query> q[maxn];
 
void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}
 
void dfs(int u) {
    sz[u] = 1;
    dep[u] = dep[par[u][0]] + 1;
    for (int j = 1; j < 22; j++) {
        par[u][j] = par[par[u][j-1]][j-1];
    }
 
    int maxsz = -1;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        dfs(to);
        sz[u] += sz[to];
        if (sz[to] > maxsz) {
            maxsz = sz[to];
            son[u] = to;
        }
    }
}
 
void add(int u, int f) {
    cnt[dep[u]] += f;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        add(to, f);
    }
}
 
void dfs2(int u, bool keep) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == son[u]) continue;
        dfs2(to, 0);
    }
    if (son[u]) dfs2(son[u], 1);
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == son[u]) continue;
        add(to, 1);
    }
    cnt[dep[u]]++;
    for (Query que : q[u]) {
        int id = que.id, d = que.d;
        ans[id] = cnt[d] - 1;
    }
    if (!keep) add(u, -1);
}
 
int jump(int u, int p) {
    for (int j = 0; (1<<j) <= p; j++) {
        if ((1<<j) & p)
            u = par[u][j];
    }
    return u;
}
 
void debug() {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 2; j++) {
            printf("i = %d, j = %d, par = %d\n",i,j,par[i][j]);
        }
    }
}
 
int main() {
    fastio;
 
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int u; cin >> u;
        if (u) {
            addEdge(u, i);
            par[i][0] = u;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!par[i][0]) dfs(i);
    }
 
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int u,p; cin >> u >> p;
        p = jump(u, p);
        int d = dep[u];  // find number of vertices in subtree of u, which has depth d
        if (!p) ans[i] = 0;
        else {
            q[p].push_back({i,d});
        }
    }
 
    for (int i = 1; i <= n; i++) {
        if (!par[i][0]) dfs2(i, 0);
    }
 
    for (int i = 1; i <= m; i++) cout << ans[i] << " ";
    cout << endl;
}

例3 CF1009F

题意

已知一棵包含 $N$ 个节点的有根树。

设 $d(u,k)$ 为 $u$ 的subtree中，到 $u$ 距离为 $k$ 的节点数量。

对于每一个点 $u$，输出一个最小的 $k$，使得 $d(u,k)$ 最大。

其中，$1\leq N \leq 10^6$

题解

注意对于这一类型的问题，有些信息看起来是 vertex-dependent（和vertex本身有关，例如 到 $u$ 距离为 $k$）。但是我们转化一下，就可以将它变成一个静态的信息，比如：

到 $u$ 距离为 $k$ $\iff$ 深度等于 $dep[u] + k$

这样，这个信息用一个 cnt[] 数组就可以继承了，例二也是同理。

用 cnt[] 数组记录每一个深度 $d$ 对应的数量，维护一个 maxcnt 和 cur，分别代表 $\max\limits_k \{d(u,k)\}$ 和 $k$ 的值。

剩下就是启发式合并的板子了。

代码 
using namespace std;
#include <bits/stdc++.h>

const int maxn = 1e6+5;
const int maxm = 2e6+10;

int head[maxn], dep[maxn], sz[maxn], son[maxn], n, ecnt = 1, cnt[maxn], ans[maxn];
struct Edge {
    int to, nxt;
} edges[maxm];

void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

void dfs1(int u, int p) {
    sz[u] = 1;
    dep[u] = dep[p] + 1;
    int maxsz = -1;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        dfs1(to, u);
        sz[u] += sz[to];
        if (sz[to] > maxsz) maxsz = sz[to], son[u] = to;
    }
}

int maxcnt = 0, cur = 1e9;

void add(int u, int f) {
    int d = dep[u];
    if (f > 0) {
        cnt[d]++;
        if (maxcnt < cnt[d]) {
            maxcnt = cnt[d];
            cur = d;
        }
        if (maxcnt == cnt[d] && cur > d) cur = d;
    } else {
        cnt[d]--;
        maxcnt = 0, cur = 1e9;
    }
}

void add(int u, int p, int f) {
    add(u,f);

    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        add(to, u, f);
    }
}

void dfs2(int u, int p, bool keep) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p || to == son[u]) continue;
        dfs2(to, u, 0);
    }
    if (son[u]) dfs2(son[u], u, 1);
    add(u, 1);

    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p || to == son[u]) continue;
        add(to, u, 1);
    }
    ans[u] = cur;
    if (!keep) add(u, p, -1);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n-1; i++) {
        int u,v; cin >> u >> v; addEdge(u,v); addEdge(v,u);
    }
    dfs1(1,0);
    dfs2(1, 0, 1);
    for (int i = 1; i <= n; i++) cout << ans[i] - dep[i] << "\n";
}

例4 CF741D

题意

已知一棵包含 $N$ 个节点的有根树，每条边上有一个字符（a-v共22种）。

定义 Dokhtar-kosh 路径为满足以下条件的路径：

  1. 简单路径（无环）
  2. 路径上的字符经过重新排序后，可以形成一个回文串

对于每一个节点 $u$，求 $u$ 所在子树中，最长的 Dokhtar-kosh 路径长度。

其中，$1\leq N \leq 5 \times 10^5$

题解

2900分的压轴题，很难。

首先定义 $f_u$ 为：从 $1$（root）开始，一直到节点 $u$ 的路径所组成的字符序列。

因为字符只有 a-v 22种，并且我们并不关心字符具体数量，只关心奇偶性，所以可以用 状压 来表示一个字符序列。

例如：$1 \rightarrow u$ 的路径上有 $a,a,b,b,b,c$，则对应的bitmask为：$000…110$（$a$有偶数个，$b,c$有奇数个）。

我们可以预处理出所有的 $f_u$，怎么得到 $u,v$ 之间路径对应的 $f$ 值？

会发现：

$$f_{u,v} = (f_u \text{ xor } f_x) \text{ xor } (f_v \text{ xor } f_x) = f_u \text{ xor } f_v$$

其中，$f_{u,v}$ 代表 $u,v$ 之间路径对应的 $f$ 值，$x = LCA(u,v)$。

又发现，一个 Dokhtar-kosh 路径只要满足：$f_{u,v}$ 所包含的 $1$ 的数量 $\leq 1$ 即可。

例如 $f_{u,v} = 000…000$ 或 $000…001$ 或 $000…010$ 等等…… 均满足条件。

所以，问题转化为：

对于每一个节点 $x$，求 $x$ 所在子树中，距离最长的 $u,v$，使得 $f_{u,v} = f_u \text{ xor } f_v$ 包含最多一个 $1$。

那么这就是一个比较标准的 树形dp 问题：

定义 $dp[mask]$ 为，在当前的节点 $x$ 的 已探索子树 中，$f_u = mask$ 的 最深深度。（因为 $x$ 太多了，所以不能定义二维数组，只能用一个全局数组）。

又发现这是关于深度的信息，可以直接向上传递，所以可以采用 树上启发式合并 进行转移。

对于每一个节点 $u$，dp的转移方程如下：

  1. 路径完全存在于某一个child的子树内：从所有的child的子树中取最大值即可！ $$ans_u = \max\limits_v \{ ans_v \}$$

  2. $u$ 本身和某一个 child 的子树中某一个节点 $v$ 组成路径： $$ans_u = \max\limits_v \{dp[f_v] + dep[u]\} - 2\times dep[u]$$

    其中 $f_u \text{ xor } f_v$ 只能包含最多一个 $1$。

  3. $u$ 的子树中有两个节点 $a,b$ 跨过了 $u$，组成一条路径： $$ans_u = \max\limits_b \{dp[f_a] + dep[b]\} - 2 \times dep[u]$$

    其中 $f_a \text{ xor } f_b$ 只能包含最多一个 $1$。

其中，Case $1,2$ 都比较好处理。对于第三种情况，我们可以在 add() 函数中，遍历子树的时候顺便处理。

注意，树形dp中一定要注意更新的先后顺序，以免出现某个节点自己和自己形成路径的情况！

代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5+5;
const int maxm = 1e6+10;
 
int head[maxn], ecnt = 1, dep[maxn], sz[maxn], son[maxn], ans[maxn], f[maxn], dp[(1<<22) + 5], masks[25], n;
struct Edge {
    int to, nxt;
    char c;
} edges[maxm];
 
void addEdge(int u, int v, char c) {
    Edge e = {v, head[u], c};
    head[u] = ecnt;
    edges[ecnt++] = e;
}
 
void dfs(int u, int p, int mask) {
    sz[u] = 1;
    dep[u] = dep[p] + 1;
    int maxsz = -1;
    f[u] = mask;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        int c = edges[e].c - 'a' + 1;
        dfs(to, u, mask ^ masks[c]);
        sz[u] += sz[to];
        if (maxsz < sz[to]) {
            maxsz = sz[to];
            son[u] = to;
        }
    }
}
 
int ori;
void add(int u, int p, int sgn) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        add(to, u, sgn);
    }
 
    if (sgn > 0) {
        for (int j = 0; j <= 22; j++) {
            int tar = f[u] ^ masks[j];
            ans[ori] = max(ans[ori], dp[tar] + dep[u]);  // 注意这里是 ori，因为更新的是 ans[ancestor]
        }
    }
 
    if (sgn < 0) dp[f[u]] = -1e9;  // 这里清空，必须初始化为负无穷
}
 
void update(int u, int p) {
    dp[f[u]] = max(dp[f[u]], dep[u]);
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        update(to, u);
    }
}
 
void add(int u) {
    for (int j = 0; j <= 22; j++) {
        int tar = f[u] ^ masks[j];
        ans[u] = max(ans[u], dp[tar] + dep[u]);  // Case 2: u 本身和 子树内某个节点
    }
}
 
void update(int u) {
    dp[f[u]] = max(dp[f[u]], dep[u]);
}
 
void dfs2(int u, int p, bool keep) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p || to == son[u]) continue;
        dfs2(to, u, 0);
    }
    if (son[u]) dfs2(son[u], u, 1);
 
    ori = u;  // Case 3: 因为 add过程中，需要更新的是 ans[u]，所以用全局变量 ori 来传递。
 
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p || to == son[u]) continue;
        add(to, u, 1);  // 树形dp注意点：先更新ans
        update(to, u);  // 更新ans后，再更新dp数组！
    }
 
    add(u);  // 注意这里单点更新
    update(u);  // 注意这里单点更新
 
    ans[u] -= 2 * dep[u];  // 这里要减去 2*dep[u]
    ans[u] = max(ans[u], 0);  // 需要大于0，因为有可能是负数
 
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        // Case1: 取每个子树的最大值
        ans[u] = max(ans[u], ans[to]);  // 注意，是在减去 2*dep[u] 以后，才取的max！
    }
    if (!keep) add(u, p, -1);
}
 
int main() {
    fastio;
 
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int p; char c; cin >> p >> c;
        addEdge(i, p, c); addEdge(p, i, c);
    }
    for (int i = 1; i <= 22; i++) masks[i] = (1<<(i-1));
    fill(dp, dp+(1<<22)+5, -1e9);
 
    dfs(1, 0, 0);
    dfs2(1, 0, 1);
 
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << endl;
}

参考链接

  1. https://blog.csdn.net/pb122401/article/details/84648993
  2. https://codeforces.com/blog/entry/44351