介绍

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

  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$。

伪代码


void dfs1(int u, int p) { //略,普通的统计 sz[] 和 son[] }

void add(int u, int f) {  // 单点更新信息
    cnt[u] += f;
    if (f < 0) maxcnt = 0;  //因为 f < 0 时意味着全局数组清空,所以一些额外的全局变量也会清空
}

void add(int u, int p, int f) {  // 遍历subtree,加到数组上。f = 1(加上信息)或者 -1(清空信息)
    add(u, f);  // 单点更新
    for (v : child[u]) {
        if (v == p) continue;
        add(v, u, f);
    }
}

void dfs2(int u, int p, bool keep) {   // keep 代表该节点是否为重儿子(如果keep = 1就不清空数组)
    for (v : child[u]) {
        if (v == p || v == son[u]) continue;
        dfs2(v, u, 0);  // Step1: 轻儿子不保留信息,keep = 0表示,在dfs2(v)结束后,全局数组不会有任何变化。
    }

    if (son[u]) dfs2(son[u], u, 1);   // Step2: 重儿子保留信息

    for (v : child[u]) {
        if (v == p || v == son[u]) continue;
        add(v, u, 1);  // Step3: 遍历所有v(除了重儿子以外),加上信息
    }

    add(u, 1);  // Step 4: 单点更新 u 的信息
    ans[u] = (cnt[u] + ...);  // Step4: 得到 ans[u]

    if (!keep) add(u, p, -1);  // 如果keep = 0,说明需要清空数组,就把整个subtree(u)的影响再减掉就可以了
}


int main() {
    init();  // 建树,预处理查询等
    dfs(1, 0);
    dfs2(1, 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$ 对应的数量,维护一个 maxcntcur,分别代表 $\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