复杂树形问题

高阶的树形问题更为困难，包括一些比较复杂的算法技巧和数据结构。

基环树

如果一个连通无向图有 $n$ 个点和 $n$ 条边，相当于在一棵树上加了一条边，长出了一个环，那么这个东西就成了基环树。除了这个基环之外，剩下的每一部分都是若干棵子树。

概念

$n$ 个点 $n$ 条边的无向图也有可能是“基环树森林”。如果图是有向的，那么还有内向基环树（每个点仅有 $1$ 条出边）和外向基环树（每个点仅有 $1$ 条入边）。

在求解与基环树相关的问题时，一般都要找到基环，把基环作为广义的“根节点”进行处理。

基环树 DP

基环树上的 DP 大致与树形 DP 一致。

[ZJOI2008] 骑士。

树的最大独立集，但是基环树。

注意这有可能是一个基环树森林，所以需要进行多次 DP。

笛卡尔树

笛卡尔树是一种特殊的 Treap，其节点权值不再是随机的，而是给定的。每个节点的权值用 $(x_i,y_i)$ 表示，只考虑 $x$ 时它是 BST，只考虑 $y$ 时它是堆（此处以小根堆为例）。

在 $x$ 递增时，我们可以以线性复杂度建出笛卡尔树。插入新节点时，为了保证 $x$ 的性质满足，要将 $x$ 插入到尽量右的地方。

具体来讲，维护一个从根节点一直走到右儿子的链。设当前需要插入 $u$ ，则需要找到第一个 $y_v<y_u$ ，将 $v$ 的右儿子设为 $u$ （不存在则将 $u$ 设为根），如果 $v$ 原本有右子树，则将 $v$ 的右子树改连在 $u$ 的左子树下面来满足 BST 性质。使用单调栈维护此链，时间复杂度为 $O(n)$ 。

模板题核心代码如下：

for (int i = 1, tot = 0, cur = 0; i <= n; ++i) {
    scanf("%d", p + i); cur = tot; 
    while (cur && p[st[cur]] > p[i]) --cur;  
    if (cur) rs[st[cur]] = i; 
    if (cur < tot) ls[i] = st[cur + 1]; // 放到左节点以满足 BST 性质
    st[++cur] = i; tot = cur; 
}

性质：如果节点编号 $1\sim n$ 为 BST 权值，然后点权满足小根堆性质，那么 $\min\{a_x,\cdots,a_y\}=a_{\operatorname{LCA}(x,y)}$ 。

树上启发式合并

还记得并查集的按秩合并吗？当秩定义为集合的大小时，就变成了启发式合并。树上启发式合并（dsu on tree）让点数小的树成为点数较大的树的子树，在处理一些可以离线的树上问题时非常简单，而且复杂度是 $\log$ 的。我们来看一道简单题：

给定一棵 $n(n\le 2\times 10^5)$ 个节点的树，节点 $x$ 的颜色是 $c_x$ ，现在询问对于 $x$ 的子树里出现了多少不同种颜色。强制离线。

我们先处理出每个子节点的子树大小和重儿子，还有当前节点子树中的最大最小时间戳，使用类似于重链剖分的过程就可以完成。用 $cnt[i]$ 表示颜色 $i$ 出现的次数， $ans[x]$ 代表节点 $x$ 的答案。

接下来我们进行第二次 dfs(x, fa, keep)， $keep$ 代表是否保留影响：

先遍历 $x$ 的轻儿子，并设置 $keep=false$ ；
遍历 $x$ 的重儿子，设置 $keep=true$ ；
将轻儿子的答案全部加入（遍历时间戳），统计答案，完成后删除。

这相当于是干了个什么呢？我们要统计一个 $x$ 子树的答案，肯定是要将它的所有儿子的也都遍历的。但问题是我们不能保留这些，遍历一个儿子的答案之后必须马上删除，否则下一个儿子的答案是错误的。而最后一个儿子的答案是不用删除的，因为马上就会回溯，这个答案肯定还要再次被使用，我们肯定选择最重的一个保留。

理论时间复杂度是 $O(n\log n)$ ，具体证明较为复杂，到时候再补吧。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

int n, siz[200005], son[200005];
int L[200005], R[200005], idx[200005], num = 0;
vector<int> G[200005];

void dfs1(int x, int fa) {
    siz[x] = 1; L[x] = ++num; idx[num] = x;
    int max_part = -1;
    for (int y : G[x]) if (y != fa) {
        dfs1(y, x); siz[x] += siz[y];
        if (siz[y] > max_part) son[x] = y, max_part = siz[y];
    }
    R[x] = num;
}

int c[200005], cnt[200005], anscol;
int ans[200005];
void add(int x) { if (cnt[c[x]] == 0) ++anscol; ++cnt[c[x]]; }
void del(int x) { if (cnt[c[x]] == 1) --anscol; --cnt[c[x]]; }

void dfs2(int x, int fa, bool keep) {
    for (int y : G[x])
        if (y != fa && y != son[x]) dfs2(y, x, false);
    if (son[x] != -1) dfs2(son[x], x, true);
    for (int y : G[x]) if (y != fa && y != son[x])
        for (int i = L[y]; i <= R[y]; ++i) add(idx[i]);
    add(x); ans[x] = anscol;
    if (!keep) for (int i = L[x]; i <= R[x]; ++i) del(idx[i]);
    // 实际上上一步会全部清空，因为当前子树中没有需要保留的内容
}

int main(void) {
    memset(son, -1, sizeof(son));
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", c + i);
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].push_back(v); G[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 0, false);
    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    putchar('\n');
    return 0;
}

Kruskal 重构树

得益于 Kruskal 的美妙性质，Kruskal 重构树是解决一些路径最值相关问题的强有力武器。

其本质上是启发式合并的一种应用。

定义

在求解 Kruskal 的时候，我们会从小到大加入若干条边。开始时我们建立 $n$ 个集合，每个集合恰好有一个节点，点权为 $0$ 。

每次加边会合并两个集合，这时候我们新建一个节点，点权为加入的边的边权，同时将两个集合的根节点分别设为新建节点的左右儿子，这时这两个集合和新建点会并为一个集合，新建点为集合的根。

当 Kruskal 完成时，我们就得到了一棵恰好包含 $n$ 个叶子的二叉树（总节点数为 $2n-1$ ），同时每个非叶子节点恰好有两个儿子，得到的这棵树就叫做 Kruskal 重构树。

性质

父亲节点的点权大于等于儿子的点权。
原图中的两点间所有简单路径上最大边权的最小值，就是最小生成树上两个点之间的简单路径上的最大边权值，就是 Kruskal 重构树上两点的 LCA 的权值。

[CF1706E] Qpwoeirut and Vertices.

根据边的顺序赋予权值，构建出 Kruskal 重构树，询问相当于求区间点的 LCA 的权值，可以使用线段树维护。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

struct edge {
    int u, v, w;
} e[200005];

int n, m, q, a[200005], bin[200005];
int find(int x) { if (bin[x] == x) return x; return bin[x] = find(bin[x]); }
vector<int> G[200005];
void addedge(int x, int fa) {
    G[x].emplace_back(fa); G[fa].emplace_back(x);
}

int f[17][200005], dep[200005], dfn[200005], num = 0;
void dfs(int x, int fa) {
    f[0][x] = fa; dep[x] = dep[fa] + 1; 
    for (int i = 1; i <= 16; ++i) f[i][x] = f[i - 1][f[i - 1][x]];
    for (int y : G[x]) if (y != fa) dfs(y, x);
}
int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 16; i >= 0; --i) if (dep[f[i][x]] >= dep[y]) x = f[i][x];
    if (x == y) return x;
    for (int i = 16; i >= 0; --i) if (f[i][x] != f[i][y]) x = f[i][x], y = f[i][y];
    return f[0][x];
}

int T[400005];
void build(int o, int l, int r) {
    if (l == r) return T[o] = l, void();
    int mid = l + r >> 1; 
    build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r);
    T[o] = LCA(T[o << 1], T[o << 1 | 1]);
}
int query(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return T[o];
    int mid = l + r >> 1;
    if (y <= mid) return query(o << 1, l, mid, x, y);
    if (mid < x) return query(o << 1 | 1, mid + 1, r, x, y);
    return LCA(query(o << 1, l, mid, x, y), query(o << 1 | 1, mid + 1, r, x, y));
}

void solve(void) {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= m; ++i) scanf("%d%d", &e[i].u, &e[i].v), e[i].w = i;
    for (int i = 1; i <= n * 2; ++i) bin[i] = i, a[i] = 0, G[i].clear();
    int tot = n;
    for (int i = 1; i <= m; ++i) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        int x = find(u), y = find(v);
        if (x == y) continue;
        a[++tot] = w; bin[x] = bin[y] = tot;
        addedge(x, tot); addedge(y, tot);
        if (tot == 2 * n - 1) break;
    }
    dfs(tot, 0);
    build(1, 1, n);
    while (q--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%d ", a[query(1, 1, n, l, r)]);
    }
    putchar('\n');
}

int main(void) {
    int T; scanf("%d", &T); while (T--) solve();
    return 0;
}

点权重构树

对于点权的限制一样可以处理。

一种选择是，限制经过的点权最大值，因为走 $(u,v)$ 需要满足均不超过 $w_u,w_v$ ，因此将边权赋值为 $\max\{w_u,w_v\}$ 。

然而事实上我们可以造一个多叉重构树。比如限制经过点权的最大值，那么将节点按照权值从小到大排序，遍历每个节点 $u$ 和能到达的节点 $v$ ，若 $v$ 已经遍历，则 $w_u\ge w_v$ ， $\max\{w_u,w_v\}$ 取到 $w_u$ ，若不连通则 $u$ 是 $v$ 所属集合的父亲。

虚树

如果树的规模很大，但是每次询问的点比较少怎么办？

引入

[SDOI2011] 消耗战。

如果查询只有一次，可以直接树形 DP：设 $f(i)$ 代表与其子树内任意询问点不连通的最小代价，如果它自己是询问点则 $f(i)=+\infty$ ，否则 $f_x=\sum_{y\in son(x)}\min\{f_y,w_{x,y}\}$ 。

但是多次询问！存在很多无用值，比如说一条链上面没有东西，我们只关心这条链的权值；还有关键点全在一棵子树内，我们根本不需要去 DP 其它子树。由于一般从根节点开始 DP，因此推荐默认把 $1$ 号节点加入虚树。

我们只需要记录关键点的 LCA 即可，这样就能完整保存树中的子孙后代关系。但是还能 $O(n^2)$ 枚举 LCA 吗？不能！将关键点按照 DFS 序排序，排序后相邻的两个关键点求 LCA 并把它加入虚树即可。但是这样很慢，可以使用一个 DFS 序递增的单调栈建立虚树：

将 $1$ 加入虚树。
如果 $dep_{lca}\le dep_{t-1}$ ，那么 $t,t-1$ 之间一定有边，不断弹栈直到条件不满足。
如果 $lca$ 不是栈顶，则将 $lca$ 向栈顶连边。
点 $p_i$ 入栈。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 

int n, m, k, dep[250005], lg[250005]; 
int mi[18][250005], dfn[250005], num, d[18][250005], fa[18][250005];
int p[250005]; bool tag[250005];
vector<pair<int, int>> G[250005]; 

int get(int x, int y) { return dep[x] < dep[y] ? x : y; }
void dfs(int x, int ff) {
    mi[0][dfn[x] = ++num] = ff; dep[x] = dep[fa[0][x] = ff] + 1;
    for (auto [y, w] : G[x]) if (y != ff) d[0][y] = w, dfs(y, x); 
}
int LCA(int u, int v) {
    if (u == v) return u;
    if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
    int k = lg[v - u];
    return get(mi[k][u + 1], mi[k][v - (1 << k) + 1]);
}

int dist(int x, int y) {
    int res = 1e9; 
    for (int i = lg[dep[y] - dep[x]]; i >= 0; --i) 
        if (dfn[fa[i][y]] >= dfn[x]) {
            res = min(res, d[i][y]);
            y = fa[i][y];
        }
    return res;
}

vector<int> E[250005];
inline void addedge(int x, int y) { // x 是父亲，y 是儿子
    E[x].emplace_back(y);
    E[y].emplace_back(x); 
}
int st[250005], tot; i64 f[250005]; 
void dp(int x, int ff) {
    if (tag[x]) f[x] = 1e15; 
    for (int y : E[x]) if (y != ff) {
        dp(y, x);
        if (!tag[x]) f[x] += min(f[y], (i64)dist(x, y));
    }
    E[x].clear();
}
void build_tree(void) {
    sort(p + 1, p + k + 1, [](int x, int y) { return dfn[x] < dfn[y]; });
    st[tot = 1] = 1; 
    for (int i = 1; i <= k; ++i) if (p[i] != 1) {
        int lca = LCA(st[tot], p[i]);
        while (tot > 1 && dep[lca] <= dep[st[tot - 1]]) addedge(st[tot - 1], st[tot]), --tot;
        if (lca != st[tot]) f[lca] = 0, addedge(lca, st[tot]), st[tot] = lca; 
        st[++tot] = p[i];
    }
    for (int i = 1; i < tot; ++i) addedge(st[i], st[i + 1]);
}

int main(void) {
    scanf("%d", &n); 
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1; 
    for (int i = 1; i < n; ++i) {
        int u, v, d; scanf("%d%d%d", &u, &v, &d);
        G[u].emplace_back(v, d); G[v].emplace_back(u, d);
    } dfs(1, 0);
    for (int i = 1; i <= lg[n]; ++i)
        for (int j = 1; j <= n; ++j) {
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
            d[i][j] = min(d[i - 1][j], d[i - 1][fa[i - 1][j]]);
            if (j + (1 << i) - 1 <= n) mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]); 
        }
    scanf("%d", &m);
    while (m--) {
        scanf("%d", &k); f[1] = 0;
        for (int i = 1; i <= k; ++i) scanf("%d", p + i), tag[p[i]] = 1, f[p[i]] = 0;
        build_tree(); 
        dp(1, 0); printf("%lld\n", f[1]); f[1] = 0; 
        for (int i = 1; i <= k; ++i) tag[p[i]] = 0;
    }
    return 0;
}

性质

点集 $S$ 的虚树边权和等于所有时间戳相邻的节点的距离之和除以 $2$ 。也就是说，设排序后的时间戳为 $a_0,\cdots a_{|S|-1}$ ，那么边权和为 $\sum_{i=0}^{|S|}dist(a_i,a_{(i+1)\bmod |S|})\div 2$ 。这其实就是 DFS 序的性质。

树上分治算法

分治又来了！树上分治算法一般分为点分治（更为常用）和边分治，类似将区间分成两半。

静态点分治

模板。

给定一棵边带权的树，多次询问树上距离为 $k$ 的点是否存在。

我们先看一看这个问题在链上如何解决：对于当前区间 $[l,r],mid=(l+r)/2$ ，答案区间 $[i,j]$ 要么满足 $i,j\le mid,i,j>mid$ ，要么跨越中点 $i\le mid<j$ 。当跨越中点时，对原序列的前缀和数组求一组 $s_j-s_i=k$ ，那么在分治的同时对 $s$ 进行归并排序，枚举 $s_j$ ，判断 $s_j-k$ 是否在 $[l,mid]$ 中出现过。时间复杂度为 $O(n\log n)$ 。

我们先任意选择一个节点作为根节点 $root$ （显然重心比较好），所有完全位于其子树中的路径可以分为：

不经过当前根节点的路径；
经过当前根节点的路径，又可以分为两种：
- 以根节点为一个端点的路径；
- 跨越根节点的路径，实际上是有两条以一个根节点为端点的路径合并而成，分治的时候只需要合并这种信息。

所以我们就可以使用类似分治的方式进行求解！找到重心 $r$ 作为分治中心，打上删除标记，并 dfs 它的每一棵子树（遇到打了删除标记的点就要立即停止）。求出子树内每个节点到分治重心的距离和来源于哪个儿子的子树，统一存在一个 vector 里，使用双指针来合并答案（注意只能合并不同的子树）。

离线统一处理可以将时间复杂度降低为 $O(n\log n(m+\log n))$ ，正常单次点分治的时间复杂度为 $O(n\log n)$ 。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int, int> pii;

int n, m, k[10005], siz[10005], maxx[10005];
int root = 0;
bool vis[10005], ans[10005];
vector<pii> G[10005];

void froot(int x, int fa, int tot) {
    siz[x] = 1; maxx[x] = 0;
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first;
        if (y == fa || vis[y]) continue;
        froot(y, x, tot); siz[x] += siz[y];
        maxx[x] = max(maxx[x], siz[y]);
    }
    maxx[x] = max(maxx[x], tot - siz[x]);
    if (maxx[x] < maxx[root]) root = x;
}

vector<pii> info;
void getinfo(int x, int fa, int anc, int d) {
    info.emplace_back(make_pair(d, anc));
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first; 
        if (y == fa || vis[y]) continue;
        getinfo(y, x, anc, d + G[x][i].second);
    }
}

void divide(int x) {
    vis[x] = true;
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first;
        if (vis[y]) continue;
        getinfo(y, x, y, G[x][i].second);
    }
    info.emplace_back(make_pair(0, x));
    sort(info.begin(), info.end());
    for (int i = 1; i <= m; ++i) {
        int l = 0, r = info.size() - 1;
        while (l < r && !ans[i]) {
            if (info[l].first + info[r].first > k[i]) --r;
            else if (info[l].first + info[r].first < k[i]) ++l;
            else {
                if (info[l].second != info[r].second) ans[i] = true;
                if (info[l].first == info[l + 1].first) ++l;
                else --r;
            }
        }
    }
    info.clear();
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first;
        if (vis[y]) continue;
        root = 0; froot(y, x, siz[y]);
        divide(root);
    }
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; ++i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        G[u].emplace_back(make_pair(v, w)); G[v].emplace_back(make_pair(u, w));
    }
    for (int i = 1; i <= m; ++i) scanf("%d", k + i);
    maxx[0] = n + 1; froot(1, 0, n); divide(root);
    for (int i = 1; i <= m; ++i) puts(ans[i] ? "AYE" :"NAY");
    return 0;
}

静态边分治

每次分治时找一条边，然后统计经过这条边的路径，再删去这条边递归统计。发现其更好地对应了序列分治（只分成了两部分）。

三度化

但是这样复杂度有问题！如果树是菊花图，那么可以被卡到 $O(n^2)$ 。此时应该对该树进行三度化，增加虚点来让该节点的度数变为 $3$ 。

动态点分治

其可以处理带修问题。

点分树

对于一个节点 $x$

长链剖分

将子树深度最大的儿子作为重儿子（虽然应该不能叫这个名字），拥有如下性质：

链的规模是 $O(\sqrt{n})$ 的。
一个节点的 $k$ 级祖先所在长链的长度一定不小于 $k$ 。
每个节点所在的长链末端是其子树内的最深节点。

树上 k 级祖先

模板。

最直接的方式就是重链剖分，然后如果链的长度 $\le k$ 就往上跳，否则直接输出（因为重链上的 DFS 序是连续的），时间复杂度为 $O(n+q\log n)$ 。

考虑长链剖分，倍增预处理出每个节点的 $2^k$ 级祖先，并对于每条长链求出其从顶端向上/向下走 $i$ 步能走到哪个节点。对于询问 $x,k$ ，先跳到 $k$ 的二进制最高位 $t$ ，即 $2^t$ 级父亲。这样可以将 $k$ 缩减一半，这样就可以直接从长链顶端根据深度开跳了。时间复杂度为 $O(n\log n + q)$ 。

查看代码

#include <bits/stdc++.h>
#define ui unsigned int
#define i64 long long
using namespace std;

ui s;
inline ui get(ui x) {
	x ^= x << 13; x ^= x >> 17; x ^= x << 5;
	return s = x; 
}

int n, q, root, lg[500005]; 
int f[19][500005], dep[500005], h[500005];
int son[500005], top[500005]; 
vector<int> G[500005], up[500005], down[500005]; 
void dfs1(int x) {
    dep[x] = dep[f[0][x]] + 1; h[x] = 1; 
    for (int i = 1; i < 19; ++i) f[i][x] = f[i - 1][f[i - 1][x]]; 
    for (int y : G[x]) {
        dfs1(y); h[x] = max(h[x], h[y] + 1); 
        if (h[son[x]] < h[y]) son[x] = y; 
    }
}
void dfs2(int x, int topf) {
    if (x == topf) up[x].resize(h[x]), down[x].resize(h[x]); 
    down[topf][dep[x] - dep[topf]] = x; top[x] = topf; 
    if (son[x]) dfs2(son[x], topf); 
    for (int y : G[x]) if (y != son[x]) dfs2(y, y); 
}

int main(void) {
    scanf("%d%d%u", &n, &q, &s); 
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1; 
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &f[0][i]); 
        if (f[0][i] == 0) root = i; 
        else G[f[0][i]].emplace_back(i); 
    }
    dfs1(root); dfs2(root, root);
    for (int i = 1; i <= n; ++i) if (top[i] == i) // 长链顶端
        for (int j = 0, cur = i; j < h[i] && cur; ++j, cur = f[0][cur])
            up[i][j] = cur; 
    i64 ans = 0; 
    for (int last = 0, i = 1; i <= q; ++i) {
        int x = (get(s) ^ last) % n + 1, k = (get(s) ^ last) % dep[x]; 
        x = (k == 0 ? x : f[lg[k]][x]), k -= (k == 0 ? 0 : (1 << lg[k]));
        int t = top[x]; 
        if (dep[x] - k >= dep[t]) last = down[t][dep[x] - k - dep[t]]; 
        else last = up[t][dep[t] - dep[x] + k];
        ans ^= 1ll * i * last; 
    }
    printf("%lld\n", ans); return 0;
}

优化深度相关的 DP

Portal.

给定一棵 $n(n\le 10^6)$ 个节点的树，设 $d(u,x)$ 为 $u$ 子树中到 $u$ 的距离为 $x$ 的节点数。对于每个点，求最小的 $k$ 使 $d(u,k)$ 最大。

我们只关心每个节点内深度为 $j$ 的节点个数，深度相同的节点是等价的。设 $f_{i,j}$ 表示子树 $i$ 内深度为 $j$ 的节点个数，则 $f_{i,j}=\sum_{k\in son(i)}f_{k,j-1}$ 。

考虑长链剖分优化：对于重儿子，直接继承它的答案。然后合并轻儿子的答案，每个节点最多被合并一次。

可以看出，这实际上是基于长链剖分的树上启发式合并，如果点只有深度信息有用的时候可以使用，时间复杂度是线性的。

查看代码

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

int n, fa[1000005], h[1000005], son[1000005]; 
int *f[1000005], buf[1000005], *poi = buf;
int ans[1000005], mx[1000005];
vector<int> G[1000005]; 

void dfs1(int x, int ff) {
    fa[x] = ff; h[x] = 1; 
    for (int y : G[x]) if (y != ff) {
        dfs1(y, x); h[x] = max(h[x], h[y] + 1); 
        if (h[son[x]] < h[y]) son[x] = y; 
    }
}

void dfs2(int x) {
    if (son[x]) f[son[x]] = f[x] + 1, dfs2(son[x]), mx[x] = mx[son[x]], ans[x] = ans[son[x]] + 1; // 长链的修改直接修改自己
    for (int y : G[x]) if (y != fa[x] && y != son[x]) {
        f[y] = poi; poi += h[y]; dfs2(y); 
        for (int i = 1; i <= h[y]; ++i) {
            f[x][i] += f[y][i - 1]; 
            if (f[x][i] > mx[x] || f[x][i] == mx[x] && ans[x] > i) mx[x] = f[x][i], ans[x] = i; 
        }
    } f[x][0] = 1; 
    if (mx[x] <= 1) mx[x] = 1, ans[x] = 0; 
}

int main(void) {
    scanf("%d", &n); 
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v); 
        G[u].emplace_back(v); G[v].emplace_back(u); 
    } dfs1(1, 0); f[1] = poi; poi += h[1]; dfs2(1); 
    for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]); 
    return 0;
}

性质

Problemset

可能会比较多。

树上启发式合并

主要用于处理一些离线不带修改的问题，还可以吊打树上莫队。

[CF600E] Lomsat gelral

Portal.

$n(n\le 10^5)$ 树的节点有颜色，一种颜色占领了一个子树，当且仅当没有其他颜色在这个子树中出现得比它多（当然可能有多个）。求占领每个子树的所有颜色编号之和。

几乎是树上启发式合并的板子，在加入的时候重新统计答案，清空的时候直接将答案清零即可。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

int n;
int c[100005], son[100005], siz[100005];
int L[100005], R[100005], idx[100005], num = 0;
vector<int> G[100005];

void dfs1(int x, int fa) {
    L[x] = ++num; idx[num] = x; siz[x] = 1;
    int max_part = -1;
    for (int y : G[x]) if (y != fa) {
        dfs1(y, x); siz[x] += siz[y];
        if (siz[y] > max_part) max_part = siz[y], son[x] = y;
    }
    R[x] = num;
}

int cnt[100005];
i64 ans[100005], nowAns, maxcnt;

void add(int x) {
    ++cnt[c[x]];
    if (cnt[c[x]] > maxcnt) maxcnt = cnt[nowAns = c[x]];
    else if (cnt[c[x]] == maxcnt) nowAns += c[x];
}

void dfs2(int x, int fa, bool keep) {
    for (int y : G[x]) 
        if (y != fa && y != son[x]) dfs2(y, x, false);
    if (son[x] != -1) dfs2(son[x], x, true);
    for (int y : G[x]) if (y != fa && y != son[x])
        for (int i = L[y]; i <= R[y]; ++i) add(idx[i]);
    add(x); ans[x] = nowAns;
    if (!keep) {
        for (int i = L[x]; i <= R[x]; ++i) --cnt[c[idx[i]]];
        maxcnt = nowAns = 0;
    }
}

int main(void) {
    memset(son, -1, sizeof(son));
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", c + i);
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].push_back(v); G[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 0, 1);
    for (int i = 1; i <= n; ++i) printf("%lld ", ans[i]);
    putchar('\n');
    return 0;
}

Kruskal 重构树

能高效解决路径最值的相关问题。

[NOI2018] 归程

Portal.

对图建立出 Kruskal 重构树，满足的点就是选择的出发点跳到满足条件的最浅的点，预处理出子树内最短路的最小值即可。

查看代码

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

int n, m;
struct edge {
    int u, v, w;
    bool operator < (const edge &a) const {
        return w > a.w;
    }
} e[400005];

struct Dijkstra {
    bool v[200005];
    int d[200005];
    vector<pair<int, int>> G[200005];
    void dijkstra(void) {
        memset(v, 0, sizeof(v)); memset(d, 0x3f, sizeof(d));
        #define pii pair<int, int>
        priority_queue<pii, vector<pii>, greater<pii>> q;
        q.push({d[1] = 0, 1});
        while (!q.empty()) {
            int u = q.top().second; q.pop();
            if (v[u]) continue; v[u] = true;
            for (int i = 0; i < G[u].size(); ++i) {
                int to = G[u][i].first, w = G[u][i].second;
                if (d[to] > d[u] + w) q.push({d[to] = d[u] + w, to});
            }
        }
    }
} Solver;

int bin[400005];
int find(int x) { if (bin[x] == x) return x; return bin[x] = find(bin[x]); }

vector<int> G[400005];
int d[400005], a[400005];
int dep[400005], f[21][400005];
void dfs(int x, int fa) {
    dep[x] = dep[fa] + 1; f[0][x] = fa; d[x] = (x <= n ? Solver.d[x] : 1e9);
    for (int i = 1; i <= 20; ++i) f[i][x] = f[i - 1][f[i - 1][x]];
    for (int y : G[x]) if (y != fa) dfs(y, x), d[x] = min(d[x], d[y]);
}
int query(int x, int y) {
    for (int i = 20; i >= 0; --i) if (a[f[i][x]] > y) x = f[i][x];
    return d[x];
}

void solve(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) Solver.G[i].clear();
    for (int i = 1; i <= n << 1; ++i) bin[i] = i, a[i] = 0, G[i].clear();
    for (int i = 1; i <= m; ++i) {
        int u, v, l, a; scanf("%d%d%d%d", &u, &v, &l, &a);
        Solver.G[u].emplace_back(make_pair(v, l));
        Solver.G[v].emplace_back(make_pair(u, l));
        e[i].u = u, e[i].v = v, e[i].w = a; 
    } Solver.dijkstra();
    sort(e + 1, e + m + 1); int tot = n;
    for (int i = 1; i <= m; ++i) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        int x = find(u), y = find(v);
        if (x == y) continue;
        a[++tot] = w; bin[x] = tot; bin[y] = tot; 
        G[x].emplace_back(tot); G[tot].emplace_back(x);
        G[y].emplace_back(tot); G[tot].emplace_back(y);
    }
    dfs(tot, 0);
    int q, k, s, last; scanf("%d%d%d", &q, &k, &s);
    while (q--) {
        int v, p; scanf("%d%d", &v, &p);
        v = (v + k * last - 1) % n + 1; p = (p + k * last) % (s + 1);
        printf("%d\n", last = query(v, p));
    }
}

int main(void) {
    int T; scanf("%d", &T); while (T--) solve();
    return 0;
}

[IOI2018] Werewolf

Portal.

是针对点权限制的 Kruskal 重构树。建立一个 $L$ 来代表子树中都比它小， $R$ 来代表子树中都比它大。将 $s$ 在 $R$ 上倍增到 $a\ge l$ 的最小 $a$ ，将 $e$ 在 $L$ 上倍增到 $b\le r$ 的最大 $b$ ，然后就是询问这两个子树有没有公共的子节点，就是二维数点问题。

查看代码

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

int n, m, q, idx[200005]; 
vector<int> G[200005]; 
vector<pair<int, int>> E[200005]; 

struct Tree {
    int bin[200005], f[21][200005]; 
    int dfn[200005], num, siz[200005]; 
    vector<int> G[200005]; 
    int find(int x) { return bin[x] == x ? x : bin[x] = find(bin[x]); }
    void init(void) { for (int i = 1; i <= n; ++i) bin[i] = i; }
    void merge(int u, int v) { // 将 v 的祖先设置为 u
        v = find(v); 
        if (u == v) return; 
        bin[v] = u; f[0][v] = u; 
        G[u].emplace_back(v); 
    }
    void dfs(int x, int fa) {
        siz[x] = 1; dfn[x] = ++num; 
        for (int i = 1; i <= 20; ++i) f[i][x] = f[i - 1][f[i - 1][x]]; 
        for (int y : G[x]) dfs(y, x), siz[x] += siz[y]; 
    }
    int query(int x, int lim, bool t) { // 将 x 跳到 t = 1 则跳到第一个 >= lim，t = 0 跳到第一个 <= lim
        for (int i = 20; i >= 0; --i)
            if (f[i][x] && (t ? f[i][x] >= lim : f[i][x] <= lim)) x = f[i][x];
        return x; 
    }
} L, R; // L 限制最大值，R 限制最小值

int C[200005], ans[200005], ql[200005], qr[200005]; 
void add(int x) { for (; x <= n; x += x & -x) ++C[x]; }
int query(int x) { int s = 0; for (; x; x -= x & -x) s += C[x]; return s; }
int query(int x, int y) { return query(y) - query(x - 1); }

int main(void) {
    scanf("%d%d%d", &n, &m, &q); 
    for (int i = 1; i <= m; ++i) {
        int u, v; scanf("%d%d", &u, &v); ++u, ++v; 
        G[u].emplace_back(v); G[v].emplace_back(u); 
    } L.init(); R.init(); 
    for (int u = 1; u <= n; ++u) for (int v : G[u]) if (u > v) L.merge(u, v); 
    for (int u = n; u >= 1; --u) for (int v : G[u]) if (u < v) R.merge(u, v);
    L.dfs(n, 0); R.dfs(1, 0); 
    for (int i = 1; i <= n; ++i) idx[L.dfn[i]] = R.dfn[i]; 
    for (int i = 1; i <= q; ++i) {
        int s, e, l, r; scanf("%d%d%d%d", &s, &e, &l, &r); ++s, ++e, ++l, ++r; 
        s = R.query(s, l, 1); e = L.query(e, r, 0); 
        E[L.dfn[e] - 1].emplace_back(i, -1); 
        E[L.dfn[e] + L.siz[e] - 1].emplace_back(i, 1); 
        ql[i] = R.dfn[s], qr[i] = R.dfn[s] + R.siz[s] - 1;
    }
    for (int i = 1; i <= n; ++i) {
        add(idx[i]); 
        for (auto [x, flag] : E[i]) ans[x] += query(ql[x], qr[x]) * flag;
    }
    for (int i = 1; i <= q; ++i) printf("%d\n", ans[i] > 0); 
    return 0;
}

[CF1583H] Omkar and Tours

Portal.

第一问比较经典，离线，将询问按照 $v$ 从大到小排序，依次加入边，DFS 合并连通块，维护最大值即可。

第二问，希望路径上 $t$ 的最大值尽可能大，Kruskal 重构树！建立一棵基于 $t$ 的边权重构树。设能到达的节点是 $y$ ，那么答案为 $\max\{a_{\operatorname{LCA}(x,y)}\}$ 。

由于 LCA 必定在 $x$ 到根节点的路径上，也就是说，我们希望该 LCA 的深度尽可能小。什么时候满足呢？将所有 $y$ 按照 DFS 序排序，其中 DFS 序最小和最大的可能称为答案（Kruskal 重构树是一棵二叉树，想要 LCA 离 $x$ 越远，那么 $y$ 就必定离 $x$ 越远，也就是 DFS 序差越大）。

实现上只需要先建出 Kruskal 重构树，然后在第一问时并查集维护 DFS 序最大最小值。时间复杂度在 $O(n\log n)$ 级别。

查看代码

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

int n, q, ans1[200005], ans2[200005]; 
int a[200005]; 
struct Query {
    int v, x, id; 
    bool operator< (const Query &a) const { return v > a.v; }
} Q[200005];
struct edge {
    int a, b, c, t; 
    bool operator< (const edge &a) const { return c > a.c; }
} e[200005];
vector<int> G[400005]; 

int bin[400005], val[400005], mx[200005], mn[200005]; 
int find(int x) { return bin[x] == x ? x : bin[x] = find(bin[x]); }

int dfn[400005], num, mi[19][400005], lg[400005], idx[400005]; 
inline int get(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
void dfs(int x, int fa) {
    mi[0][dfn[x] = ++num] = fa; idx[num] = x; 
    for (int y : G[x]) if (y != fa) dfs(y, x); 
}
inline int LCA(int u, int v) {
    if (u == v) return u; 
    if ((u = dfn[u]) > (v = dfn[v])) swap(u, v); 
    int k = lg[v - u]; 
    return get(mi[k][u + 1], mi[k][v - (1 << k) + 1]); 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> q; 
    for (int i = 1; i <= n; ++i) cin >> a[i]; 
    for (int i = 1; i <= n * 2; ++i) bin[i] = i; 
    for (int i = 2; i <= n * 2; ++i) lg[i] = lg[i >> 1] + 1; 

    // 建立 Kruskal 重构树
    for (int i = 1; i < n; ++i) cin >> e[i].a >> e[i].b >> e[i].c >> e[i].t; 
    sort(e + 1, e + n, [&](edge a, edge b) { return a.t < b.t; });    
    int tot = n; 
    for (int i = 1; i < n; ++i) {
        int u = find(e[i].a), v = find(e[i].b); 
        val[++tot] = e[i].t; bin[u] = bin[v] = tot; 
        G[tot].emplace_back(u); G[u].emplace_back(tot); 
        G[tot].emplace_back(v); G[v].emplace_back(tot); 
    } dfs(tot, 0); 
    for (int i = 1; i <= lg[n * 2]; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n * 2 - 1; ++j)
            mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]); 
    
    for (int i = 1; i <= q; ++i) cin >> Q[i].v >> Q[i].x, Q[i].id = i; 
    for (int i = 1; i <= n; ++i) bin[i] = i, val[i] = a[i], mn[i] = mx[i] = dfn[i]; 
    sort(e + 1, e + n); sort(Q + 1, Q + q + 1); 
    for (int i = 1, j = 0; i <= q; ++i) {
        while (j < n - 1 && e[j + 1].c >= Q[i].v) {
            ++j; 
            int u = find(e[j].a), v = find(e[j].b); 
            if (val[u] == val[v]) mx[v] = max(mx[v], mx[u]); 
            else mx[v] = val[u] > val[v] ? mx[u] : mx[v]; 
            if (val[u] == val[v]) mn[v] = min(mn[v], mn[u]); 
            else mn[v] = val[u] > val[v] ? mn[u] : mn[v]; 
            val[v] = max(val[v], val[u]); 
            bin[u] = v; 
        }
        int id = Q[i].id, x = Q[i].x, u = find(x); 
        ans1[id] = val[u]; 
        if (idx[mx[u]] != x) ans2[id] = max(ans2[id], val[LCA(x, idx[mx[u]])]);
        if (idx[mn[u]] != x) ans2[id] = max(ans2[id], val[LCA(x, idx[mn[u]])]); 
    }

    for (int i = 1; i <= q; ++i) cout << ans1[i] << " " << ans2[i] << "\n"; 
    return 0; 
}

虚树

这里的不会很难，难的虚树会和别的树上算法综合。

[HEOI2014] 大工程

Portal.

建出虚树后进行 DP，设 $sz_x,mn_x,mx_x$ 分别代表子树内关键点个数，当前节点到关键点的最小和最大距离，用它们更新 $ans$ 即可。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 

int n, k, q, lg[1000005], p[1000005];
int dep[1000005];
int dfn[1000005], num, mi[20][1000005]; 
vector<int> G[1000005];

inline int get(int x, int y) { return dep[x] < dep[y] ? x : y; }
void dfs(int x, int fa) {
    mi[0][dfn[x] = ++num] = fa; dep[x] = dep[fa] + 1; 
    for (int y : G[x]) if (y != fa) dfs(y, x);
}
int LCA(int u, int v) {
    if (u == v) return u; 
    if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
    int k = lg[v - u];
    return get(mi[k][u + 1], mi[k][v - (1 << k) + 1]);
}

int st[1000005], tot, ans2, ans3; i64 ans1; 
int sz[1000005], mx[1000005], mn[1000005];
vector<int> E[1000005];
inline void addedge(int x, int y) {
    E[x].emplace_back(y);
    E[y].emplace_back(x); 
}
void dp(int x, int fa) {
    for (int y : E[x]) if (y != fa) {
        dp(y, x); int d = dep[y] - dep[x]; 
        ans1 += 1ll * sz[y] * (k - sz[y]) * d;
        ans2 = min(ans2, mn[x] + mn[y] + d);
        ans3 = max(ans3, mx[x] + mx[y] + d);
        
        mn[x] = min(mn[x], mn[y] + d); 
        mx[x] = max(mx[x], mx[y] + d);
        sz[x] += sz[y]; 
    }
    E[x].clear();
}
void build_tree(void) {
    sort(p + 1, p + k + 1, [&](int x, int y) { return dfn[x] < dfn[y]; });
    st[tot = 1] = 1; if (p[1] != 1) sz[1] = 0, mn[1] = 1e9, mx[1] = -1e9; 
    for (int i = 1; i <= k; ++i) if (p[i] != 1) {
        int lca = LCA(st[tot], p[i]);
        while (tot > 1 && dep[lca] <= dep[st[tot - 1]]) addedge(st[tot - 1], st[tot]), --tot; 
        if (lca != st[tot]) {
            sz[lca] = 0; mn[lca] = 1e9; mx[lca] = -1e9; 
            addedge(lca, st[tot]), st[tot] = lca; 
        }
        st[++tot] = p[i];
    }
    for (int i = 1; i < tot; ++i) addedge(st[i], st[i + 1]); 
}

int main(void) {
    scanf("%d", &n);
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1; 
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].emplace_back(v); G[v].emplace_back(u);
    } dfs(1, 0);
    for (int i = 1; i <= lg[n]; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
            mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
    scanf("%d", &q);
    while (q--) {
        scanf("%d", &k); ans1 = ans3 = 0, ans2 = 1e9;
        for (int i = 1; i <= k; ++i)    
            scanf("%d", p + i), sz[p[i]] = 1, mn[p[i]] = mx[p[i]] = 0; 
        build_tree(); dp(1, 0);
        printf("%lld %d %d\n", ans1, ans2, ans3); 
    }
    return 0;
}

[CF613D] Kingdom and its Cities

Portal.

首先如果关键点相邻直接无解，否则设计 DP： $g(x)$ 为以 $x$ 为根，子树内是否有关节点； $f(x)$ 为以 $x$ 为根的答案。

如果 $x$ 是关键点，那么儿子内有关键点的需要全部断掉。若不是关键点，儿子内有超过两个关键点则直接删掉自己（否则就连上了），否则可以留到父亲处再做考虑。

查看代码

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

int n, m, k, p[100005], lg[100005]; 
int tot, st[100005], tag[100005], fa[100005]; 
int dfn[100005], num, mi[17][100005], dep[100005]; 
vector<int> E[100005], G[100005];
inline void addedge(int x, int y) {
    G[x].emplace_back(y); G[y].emplace_back(x); 
}

inline int get(int x, int y) { return dep[x] < dep[y] ? x : y; }
void dfs(int x, int ff) {
    mi[0][dfn[x] = ++num] = ff; fa[x] = ff; dep[x] = dep[ff] + 1; 
    for (int y : E[x]) if (y != ff) dfs(y, x);
}
int LCA(int u, int v) {
    if (u == v) return u;
    if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
    int k = lg[v - u];
    return get(mi[k][u + 1], mi[k][v - (1 << k) + 1]);
}

int f[100005], g[100005]; 
void build_tree(void) {
    sort(p + 1, p + k + 1, [](int x, int y){ return dfn[x] < dfn[y]; }); 
    st[tot = 1] = 1; f[1] = g[1] = 0; 
    for (int i = 1; i <= k; ++i) if (p[i] != 1) {
        int lca = LCA(st[tot], p[i]);
        while (tot > 1 && dep[lca] <= dep[st[tot - 1]]) addedge(st[tot - 1], st[tot]), --tot;
        if (lca != st[tot]) addedge(lca, st[tot]), st[tot] = lca, f[lca] = g[lca] = 0;
        st[++tot] = p[i];
    }
    for (int i = 1; i < tot; ++i) addedge(st[i], st[i + 1]);
}
void dp(int x, int fa) {
    int num = 0;
    for (int y : G[x]) if (y != fa) {
        dp(y, x); f[x] += f[y]; 
        num += g[y]; 
    }
    if (tag[x]) f[x] += num, g[x] = 1; // 将儿子全断掉
    else if (num > 1) ++f[x], g[x] = 0; 
    else g[x] = num;
    G[x].clear();
}

int main(void) {
    scanf("%d", &n); 
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1; 
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v); 
        E[u].emplace_back(v); E[v].emplace_back(u); 
    } dfs(1, 0); 
    for (int i = 1; i <= lg[n]; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
            mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
    scanf("%d", &m);
    while (m--) {
        scanf("%d", &k);
        for (int i = 1; i <= k; ++i) scanf("%d", p + i), tag[p[i]] = 1, f[p[i]] = g[p[i]] = 0;
        for (int i = 1; i <= k; ++i) if (tag[fa[p[i]]]) { puts("-1"); goto over; }
        build_tree(); dp(1, 0); printf("%d\n", f[1]);
        over:
        for (int i = 1; i <= k; ++i) tag[p[i]] = 0; 
    }
    return 0;
}

树上分治算法

部分题目相当复杂，但是对训练非常有益。

[Luogu P4178] Tree

Portal.

似乎使用双指针计算比较难防止算重同一棵子树内的点，于是我们在采集子树信息的时候直接算一遍子树内的贡献，减去它就好了。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int, int> pii;

int n, k, root, siz[40005], mx[40005], ans = 0;
bool vis[40005];
vector<pii> G[40005];

void froot(int x, int fa, int tot) {
    siz[x] = 1; mx[x] = 0;
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first;
        if (y == fa || vis[y]) continue;
        froot(y, x, tot); siz[x] += siz[y];
        mx[x] = max(mx[x], siz[y]);
    }
    mx[x] = max(mx[x], tot - siz[x]);
    if (mx[root] > mx[x]) root = x;
}

int calc(vector<int> &val) {
    int res = 0;
    sort(val.begin(), val.end());
    for (int l = 0, r = val.size() - 1; l < r; ++l) {
        while (l < r && val[l] + val[r] > k) --r;
        res += r - l;
    }
    return res;
}

vector<int> val, t;
void getinfo(int x, int fa, int anc, int d) {
    t.push_back(d);
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first;
        if (y == fa || vis[y]) continue;
        getinfo(y, x, anc, d + G[x][i].second);
    }
}

void divide(int x) {
    vis[x] = true;
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first;
        if (vis[y]) continue;
        t.clear(); getinfo(y, x, y, G[x][i].second);
        ans -= calc(t);
        for (int z : t) val.push_back(z);
    }
    val.push_back(0);
    ans += calc(val);
    val.clear();
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first;
        if (vis[y]) continue;
        root = 0; froot(y, x, siz[y]); divide(root);
    }
}

int main(void) {
    scanf("%d", &n); mx[0] = n + 1;
    for (int i = 1; i < n; ++i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        G[u].push_back({v, w}); G[v].push_back({u, w});
    }
    scanf("%d", &k); froot(1, 0, n); divide(root);
    printf("%d\n", ans);
    return 0;
}

[IOI2011] Race

Portal.

由于 $k$ 不是很大，开一个桶记录权值对应的最小边数即可。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
const int MAXD = 1000005;
typedef pair<int, int> pii;

int n, k, ans, root;
int siz[200005], maxx[200005];
int buc[1000005];
bool vis[200005];
vector<pii> G[200005];

void froot(int x, int fa, int tot) {
    siz[x] = 1; maxx[x] = 0;
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first;
        if (y == fa || vis[y]) continue;
        froot(y, x, tot); siz[x] += siz[y];
        maxx[x] = max(maxx[x], siz[y]);
    }
    maxx[x] = max(maxx[x], tot - siz[x]);
    if (maxx[x] < maxx[root]) root = x;
}

vector<pii> f[200005];
void getinfo(int x, int fa, int anc, int d, int cnt) {
    f[anc].emplace_back(make_pair(d, cnt));
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first;
        if (vis[y] || y == fa) continue;
        getinfo(y, x, anc, min(MAXD, d + G[x][i].second), cnt + 1);
    }
}

void divide(int x) {
    vis[x] = true;
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first;
        if (vis[y]) continue;
        getinfo(y, x, y, G[x][i].second, 1);
        for (pii info : f[y]) {
            int dis = info.first, w = info.second;
            if (dis <= k) ans = min(ans, buc[k - dis] + w);
        }
        for (pii info : f[y]) {
            int dis = info.first, w = info.second;
            if (dis <= k) buc[dis] = min(buc[dis], w);
        }
    }
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first;
        if (vis[y]) continue;
        for (pii info : f[y]) buc[info.first] = 0x3f3f3f3f;
        f[y].clear();
    }
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first;
        if (vis[y]) continue;
        root = 0; froot(y, x, siz[y]); divide(root);
    }
}

int main(void) {
    scanf("%d%d", &n, &k); memset(buc, 0x3f, sizeof(buc)); buc[0] = 0;
    for (int i = 1; i < n; ++i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w); ++u, ++v;
        G[u].emplace_back(make_pair(v, w));
        G[v].emplace_back(make_pair(u, w));
    }
    ans = maxx[0] = n + 1; froot(1, 0, n); divide(root);
    if (ans == n + 1) puts("-1");
    else printf("%d\n", ans);
    return 0;
}

[省选联考 2020 B 卷] 消息传递

Portal.

我们给所有节点开一个 vector 来保存询问，然后对传播路径是否经过当前点 $x$ 进行分治。获取子树信息时，我们将当前距离 $d$ 加在一个桶中，每扫描到一个节点 $i$ 都查看当前节点的询问，它应该满足 $k\ge d$ ，在获取完所有信息后在桶中查 $k-d$ 的数量来获取答案。

查看代码

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

int n, m, root, siz[100005], maxx[100005], ans[100005]; 
bool vis[100005]; 
vector<int> G[100005]; 
vector<pair<int, int>> Q[100005]; // x, id

void froot(int x, int fa, int tot) {
    siz[x] = 1; maxx[x] = 0; 
    for (int y : G[x]) if (y != fa && !vis[y]) {
        froot(y, x, tot); siz[x] += siz[y]; 
        maxx[x] = max(maxx[x], siz[y]); 
    }
    maxx[x] = max(maxx[x], tot - siz[x]); 
    if (maxx[x] < maxx[root]) root = x; 
}

vector<pair<int, int> > info; 
int buc[100005], maxd; 
void getinfo(int x, int fa, int d) {
    ++buc[d]; maxd = max(d, maxd); 
    for (auto [k, id] : Q[x]) if (k - d >= 0) info.emplace_back(k - d, id); // 找当前这个点的询问
    for (int y : G[x]) if (y != fa && !vis[y]) getinfo(y, x, d + 1); 
}
void divide(int x) {
    vis[x] = true;
    for (int y : G[x]) if (!vis[y]) {
        getinfo(y, x, 1);
        for (auto [k, id] : info) ans[id] -= buc[k];
        for (int i = 0; i <= maxd; ++i) buc[i] = 0;
        maxd = 0; info.clear();
    }
    getinfo(x, 0, 0); 
    for (auto [k, id] : info) ans[id] += buc[k];
    for (int i = 0; i <= maxd; ++i) buc[i] = 0; 
    maxd = 0; info.clear();

    for (int y : G[x]) if (!vis[y]) {
        root = 0; froot(y, x, siz[y]); 
        divide(root);
    }
}

int main(void) {
    int T; scanf("%d", &T); 
    while (T--) {
        scanf("%d%d", &n, &m); maxx[0] = n + 1;
        for (int i = 1; i <= n; ++i) G[i].clear(), Q[i].clear(), vis[i] = 0; 
        for (int i = 1; i < n; ++i) {
            int u, v; scanf("%d%d", &u, &v); 
            G[u].emplace_back(v); G[v].emplace_back(u);
        }
        for (int i = 1; i <= m; ++i) {
            int x, k; scanf("%d%d", &x, &k);
            Q[x].emplace_back(k, i); 
            ans[i] = 0; 
        }
        root = 0; froot(1, 0, n); divide(root); 
        for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]); 
    }
    return 0;
}

[SDOI2016] 模式字符串

Portal.

点分治，然后使用字符串 Hash 来判断是否能作为模式串的前后缀，然后用一个桶来统计进行答案合并。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;
const int N = 1000000;
typedef unsigned long long u64;

int n, m, root, ans;
char s[1000005], t[1000005];
int maxx[1000005], siz[1000005], buc[1000005];
u64 poww[1000005], pre[1000005], suf[1000005];
bool vis[1000005];
vector<int> G[1000005];

void froot(int x, int fa, int tot) {
    siz[x] = 1; maxx[x] = 0;
    for (int y : G[x]) if (y != fa && !vis[y]) {
        froot(y, x, tot); siz[x] += siz[y];
        maxx[x] = max(maxx[x], siz[y]);
    }
    maxx[x] = max(maxx[x], tot - siz[x]);
    if (maxx[x] < maxx[root]) root = x;
}

int calc(vector<int> &x, vector<int> &y) {
    int res = 0;
    for (int it : x) ++buc[1 + (it - 1) % m];
    for (int it : y) res += buc[m - (it - 1) % m];
    for (int it : x) --buc[1 + (it - 1) % m];
    return res;
}

vector<int> p, q, pt, qt;
void getinfo(int x, int fa, u64 hash, int dep) {
    hash += s[x] * poww[dep - 1];
    if (pre[dep] == hash) pt.emplace_back(dep);
    if (suf[dep] == hash) qt.emplace_back(dep);
    for (int y : G[x]) if (y != fa && !vis[y])
        getinfo(y, x, hash, dep + 1);
}

void divide(int x) {
    vis[x] = true; p.clear(); q.clear();
    if (s[x] == t[1]) p.emplace_back(1);
    if (s[x] == t[m]) q.emplace_back(1);
    for (int y : G[x]) if (!vis[y]) {
        getinfo(y, x, s[x], 2);
        ans -= calc(pt, qt);
        for (int it : pt) p.emplace_back(it);
        for (int it : qt) q.emplace_back(it);
        pt.clear(); qt.clear();
    }
    ans += calc(p, q);
    for (int y : G[x]) if (!vis[y]) {
        root = 0; froot(y, x, siz[y]);
        divide(root);
    }
}

void solve(void) {
    scanf("%d%d%s", &n, &m, s + 1); maxx[0] = n + 1;
    for (int i = 1; i <= n; ++i) G[i].clear();
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].emplace_back(v); G[v].emplace_back(u);
    }
    scanf("%s", t + 1); 
    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1] * 239 + t[1 + (i - 1) % m];
        suf[i] = suf[i - 1] * 239 + t[m - (i - 1) % m];
    }
    memset(vis, 0, sizeof(vis)); ans = root = 0;
    froot(1, 0, n); divide(root);
    printf("%d\n", ans);
}

int main(void) {
    for (int i = poww[0] = 1; i <= N; ++i) poww[i] = poww[i - 1] * 239;
    int T; scanf("%d", &T); while (T--) solve();
    return 0;
}

[CF914E] Palindromes in a Tree

Portal.

只要出现奇数次的字符最多只有一个，那么就可以重排为回文，可以状压来统计字符的奇偶性。

对回文路径是否经过点 $pos$ 进行点分治，获取子树状压的字符信息放在 vector 里，在统计答案时将异或信息放在桶里。点的答案要加上子树的答案，因为子树的回文路径也会经过这个点。

子树的会算重，因此提前减去。分治重心的答案的两个端点在不同子树答案会算重，因此除以二。分治重心自己也可以称为答案，要加一。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 

int n, root, mx[200005], siz[200005]; 
i64 ans[200005], d[200005]; 
char s[200005]; 
bool vis[200005]; 
vector<int> G[200005]; 

void froot(int x, int fa, int tot) {
    mx[x] = 0; siz[x] = 1; 
    for (int y : G[x]) if (y != fa && !vis[y]) {
        froot(y, x, tot); siz[x] += siz[y]; 
        mx[x] = max(mx[x], siz[y]); 
    }
    mx[x] = max(mx[x], tot - siz[x]); 
    if (mx[x] < mx[root]) root = x; 
}

int buc[1 << 20]; 
void calc(vector<pair<int, int>> &a, int flag, int msk) {
    for (auto it : a) buc[it.first] += flag; 
    for (auto [x, pos] : a) {
        int cnt = buc[x ^ msk]; // 排掉分治中心统计另一端
        for (int i = 0; i < 20; ++i) cnt += buc[x ^ msk ^ (1 << i)]; 
        d[pos] += cnt; 
    }
    for (auto it : a) buc[it.first] = 0; 
}

vector<pair<int, int>> info, q; 
void getinfo(int x, int fa, int msk) {
    d[x] = 0; msk ^= 1 << s[x]; q.emplace_back(msk, x); 
    for (int y : G[x]) if (y != fa && !vis[y]) getinfo(y, x, msk); 
}
void getans(int x, int fa) {
    for (int y : G[x]) if (y != fa && !vis[y]) {
        getans(y, x); 
        d[x] += d[y]; 
    }
    if (!fa) d[x] = d[x] / 2 + 1; 
    ans[x] += d[x]; 
}
void divide(int x) {
    vis[x] = 1; d[x] = 0; 
    int msk = 1 << s[x]; 

    for (int y : G[x]) if (!vis[y]) {
        getinfo(y, x, msk); calc(q, -1, msk); 
        for (auto tmp : q) info.emplace_back(tmp);
        q.clear(); 
    }
    info.emplace_back(msk, x); calc(info, 1, msk); 
    info.clear(); getans(x, 0); 

    for (int y : G[x]) if (!vis[y]) {
        root = 0; froot(y, x, siz[y]); 
        divide(root); 
    }
}

int main(void) {
    scanf("%d", &n); mx[0] = n + 1; 
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v); 
        G[u].emplace_back(v); G[v].emplace_back(u); 
    }
    scanf("%s", s + 1); 
    for (int i = 1; i <= n; ++i) s[i] -= 'a'; 
    froot(1, 0, n); divide(root); 
    for (int i = 1; i <= n; ++i) printf("%lld ", ans[i]);
    putchar('\n'); return 0;
}

复杂树上乱搞

非常奇怪，但很有趣。

在思考这些内容时，请回顾树上问题的常见处理手段：

[CF1580D] Subsequence

Portal.

先来看一下要求的这个东西：

$\begin{aligned} \text{原式}&=\sum_{i = 1}^m (m \cdot a_{b_i}) - \sum_{i = 1}^m \sum_{j = 1}^m f(\min(b_i, b_j), \max(b_i, b_j))\\ &=(m-1)\sum_{i = 1}^m a_{b_i}-2\sum_{i=1}^m\sum_{j=i+1}^m \min\{a_{b_i},a_{b_i+1}\cdots,a_{b_j-1},a_{b_j}\} \end{aligned}$

要求这个东西的最大值，后面这个区间最小值可以考虑放到笛卡尔树上，然后用树形 DP 求解这个问题。

设 $f_{x,k}$ 代表 $x$ 中选择 $k$ 个节点的最大价值，初始 $f_{i,1}=(m-1)a_i$ ，然后转移是一个类似树形背包的过程：

$f_{x,i+j}=\max\{f_{x,i}+f_{y,j}-2\times a_x\times i\times j\}$

查看代码

#include <bits/stdc++.h>
using namespace std; 
typedef long long i64; 
inline void ckmax(i64 &x, i64 t) { if (x < t) x = t; }

int n, m, rt; 
int a[4005], ls[4005], rs[4005], st[4005], siz[4005]; 
i64 f[4005][4005]; 
bool v[4005]; 

void dfs(int x) {
	f[x][1] = 1ll * (m - 1) * a[x]; siz[x] = 1; 
	function<void(int)> work = [&] (int y) {
		dfs(y); 
		for (int i = siz[x]; i >= 0; --i)
			for (int j = 0; j <= siz[y]; ++j)
				ckmax(f[x][i + j], f[x][i] + f[y][j] - 2ll * a[x] * i * j); 
		siz[x] += siz[y]; 
	}; 
	if (ls[x]) work(ls[x]); if (rs[x]) work(rs[x]); 
}

int main(void) {
	scanf("%d%d", &n, &m); 
	for (int i = 1, cur = 0, tot = 0; i <= n; ++i) {
		scanf("%d", a + i); cur = tot; 
		while (cur && a[st[cur]] > a[i]) --cur; 
		if (cur) rs[st[cur]] = i; 
		if (cur < tot) ls[i] = st[cur + 1]; 
		st[++cur] = i; tot = cur; 
	}
	for (int i = 1; i <= n; ++i) v[ls[i]] = v[rs[i]] = 1; 
	for (int i = 1; i <= n; ++i) if (!v[i]) dfs(i), printf("%lld\n", f[i][m]); 
	return 0;  
}

[CF983E] NN country

Portal.

考虑在链上怎么做。贪心的乘坐能到达的最远的车，并使用倍增加速。放到树上就是预处理出数组 $g_{i,j}$ 表示乘坐 $i+1$ 次车，从 $j$ 能到达的最浅节点。

特判掉 $u,v$ 其中一个是另一个的祖先的情况，我们让 $u,v$ 分别乘坐到它们 LCA 的底下，然后再乘坐两次车就可以到了。但是如果有一辆车可以直接从一个子树到另一个子树，那么可以选择乘坐它。这样就成了一个二维数点问题，判断两棵子树内是否有相同的公交车，DFS 序加主席树即可在线维护。

查看代码

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

int n, m, q, lg[200005], dep[200005], g[18][200005];
int f[200005], mi[18][200005], dfn[200005], num, L[200005], R[200005];  
vector<int> G[200005], bus[200005]; 

inline int get(int x, int y) { return dep[x] < dep[y] ? x : y; }
void dfs(int x, int fa) {
    mi[0][dfn[x] = L[x] = ++num] = fa; dep[x] = dep[fa] + 1;
    for (int y : G[x]) dfs(y, x); R[x] = num; 
}
int LCA(int u, int v) {
    if (u == v) return u; 
    if ((u = dfn[u]) > (v = dfn[v])) swap(u, v); 
    int k = lg[v - u]; 
    return get(mi[k][u + 1], mi[k][v - (1 << k) + 1]); 
}

struct Node {
    int ls, rs; 
    int val; 
} T[40 * 200005];
int root[200005], tot; 
int build(int l, int r) {
    int o = ++tot; if (l == r) return o;
    int mid = l + r >> 1; T[o].ls = build(l, mid); T[o].rs = build(mid + 1, r); 
    return o; 
}
int update(int pre, int l, int r, int x) {
    int o = ++tot; T[tot] = T[pre]; T[tot].val++; 
    if (l == r) return o;
    int mid = l + r >> 1; 
    if (x <= mid) T[o].ls = update(T[pre].ls, l, mid, x); 
    else T[o].rs = update(T[pre].rs, mid + 1, r, x); 
    return o; 
}
int query(int o, int l, int r, int x, int y) {
    if (!o) return 0; 
    if (x <= l && r <= y) return T[o].val; 
    int mid = l + r >> 1, res = 0; 
    if (x <= mid) res += query(T[o].ls, l, mid, x, y); 
    if (mid < y) res += query(T[o].rs, mid + 1, r, x, y); 
    return res; 
}

int main(void) {
    scanf("%d", &n); 
    for (int i = 2; i <= n; ++i) {
        scanf("%d", f + i); G[f[i]].emplace_back(i); 
        lg[i] = lg[i >> 1] + 1; 
    } dfs(1, 0); 
    for (int i = 1; i <= lg[n]; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
            mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
    scanf("%d", &m); 
    for (int i = 1; i <= n; ++i) g[0][i] = i;
    for (int i = 1; i <= m; ++i) {
        int x, y; scanf("%d%d", &x, &y); 
        int l = LCA(x, y); 
        g[0][x] = min(g[0][x], l); g[0][y] = min(g[0][y], l); 
        bus[dfn[x]].emplace_back(dfn[y]); bus[dfn[y]].emplace_back(dfn[x]); 
    }
    for (int i = n; i >= 1; --i) g[0][f[i]] = min(g[0][f[i]], g[0][i]); 
    for (int i = 1; i <= lg[n]; ++i)
        for (int j = 1; j <= n; ++j)
            g[i][j] = g[i - 1][g[i - 1][j]]; 
    root[0] = build(1, n); 
    for (int i = 1; i <= n; ++i) {
        root[i] = root[i - 1]; 
        for (int k : bus[i]) root[i] = update(root[i], 1, n, k); 
    }
    scanf("%d", &q); 
    while (q--) {
        int u, v; scanf("%d%d", &u, &v); 
        if (u == v) { puts("0"); continue; }
        int l = LCA(u, v); 
        if (g[lg[n]][u] > l || g[lg[n]][v] > l) { puts("-1"); continue; } // 跳不到 LCA 上，无答案
        int ans = 2; 
        for (int i = lg[n]; i >= 0; --i) if (g[i][u] > l) u = g[i][u], ans += 1 << i; 
        for (int i = lg[n]; i >= 0; --i) if (g[i][v] > l) v = g[i][v], ans += 1 << i; 
        if (u == l || v == l) --ans; 
        else ans -= (query(root[R[u]], 1, n, L[v], R[v]) - query(root[L[u] - 1], 1, n, L[v], R[v])) > 0; 
        printf("%d\n", ans); 
    }
    return 0;
}