简介
大概就是跟树有关的东西吧 = =
LCA
倍增
$O(n\log n)$ 预处理，$O(\log n)$ 查询
1 | int f[maxn][21], dep[maxn]; |
树剖
$O(n)$ 预处理，$O(\log n)$ 查询
据说常数小
1 | int dep[maxn], son[maxn], sz[maxn], f[maxn]; |
RMQ 求 lca
$O(n\log n)$ 预处理，$O(1)$ 查询
1 | namespace LCA { |
tarjan 离线
$O(n)$
1 | int ans[maxn]; bool vis[maxn]; |
prufer 序列
简介
给定一颗带标号无根树，找出编号最小的叶子节点，写下与它相邻的点的编号，然后删掉这个叶子节点。反复执行这个操作直到只剩两个节点为止
可以证明这样得到所有长度为 $n-2$ 的序列都唯一对应一棵带标号无根树，且在 $prufer$ 序列中的每个数的出现次数是它在原树中的度数减一
同时这样我们也得到了 $n$ 个点的所有带标号无根树的个数为 $n^{n-2}$
拓展
给定每个点的度数 $d_i$，求有多少带标号无根树
$ans=\frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}$
例题
简要题意：给定一棵大小为 $n$ 的树和 $k$，要求断掉给定的 $n-1$ 条边的中 $k$ 条边，之后在连 $k$ 条边使得仍然构成一棵大小为 $n$ 的树,求有多少种连边方法
$n\le 5\times 10^4,k\le 100$
简要题解：
$ans=\sum_{\pi=\lbrace S_1,S_2,\cdots,S_{k+1}\rbrace}\sum_{p\in prufer(k+1)}\prod_{i=1}^{k+1}|S_i|^{p_i+1}$
$\pi$ 表示对于原树切掉 $k$ 条边后得到的 $k$ 个子树， $prufer(k+1)$ 表示 $k+1$ 个点所有 $prufer$ 序列，$p_i$ 表示 $i$ 在 $prufer$ 序列中出现的次数
化简可以的得到 $ans=n^{k-1}\sum_{\pi=\lbrace S_1,S_2,\cdots,S_{k+1}\rbrace}\prod_{i=1}^{k+1}|S_i|$
树的重心
性质
- 树上所有点到某点的距离和中，到重心的距离和最小，如果有两个重心，他们的距离和相等
- 一棵树添加或者删除一个节点，树的重心最多最多只移动一条边的位置
- 把两棵树通过某一点相连得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上
- 一棵树最多有两个重心，且一定相邻，且此时重心的最大子树的大小为 $\frac{n}{2}$
- 以重心为根，最大的儿子的子树的大小不超过 $\frac{n}{2}$
例题
简要题意：给定一棵 $n$ 个节点的树，求是否可以通过删一条边并且加一条边使得该树的重心唯一，删掉的边和加入的边可以是同一条边
$n\le 10^5$
简要题解：根据树的重心的性质，如果有两个重心 $x$ 和 $y$，则 $x$ 和 $y$ 一定直接相连
所以我们不妨砍掉 $y$ 里的一个叶子然后连到 $x$ 上，这样重心就变成了 $x$
简要题意：给定 $n$ 个点，现在有 $m$ 次操作，操作有三种，第一种操作给定两个点 $x,y$，加入一条连接 $x$ 和 $y$ 的边，保证连边后仍然是森林；第二种操作给定一个点 $x$，求 $x$ 所在连通块的重心，如果有两个重心输出编号较小的那个；第三种操作求所有连通块重心的编号的异或和
$n\le 10^5,m\le 2\times 10^5$
简要题解：根据重心的性质，把两棵树通过某一点相连得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上，那么我们使用并查集维护每个连通块的重心，每次合并时用 $LCT$ 把两个重心所在的路径拉出来，然后我们在这个路径上二分
这里的二分是在 $Splay$ 上进行的，我们从根节点开始进行，然后我们比较以该节点为整棵树的根时，它的左子树的大小和右子树的大小，然后我们选择较大的进入即可，需要注意在进入子树时需要维护被扔掉的子树的信息
时间复杂度 $O(n\log n)$
1
2
3
4
5
6
7
8
9
10int solve(int x, int y) {
split(x, y); int sum = T[y].v, i = y, lv = 0, rv = 0, res = INF;
while (i) {
push(i);
int L = lv + T[lc].v, R = rv + T[rc].v;
if (max(L, R) <= sum / 2) res = min(res, i);
if (L > R) rv += T[rc].v + T[i].sv + T[i].val, i = lc;
else lv += T[lc].v + T[i].sv + T[i].val, i = rc;
} return Splay(res), res;
}
树的直径
性质
- 直径的两个端点一是叶子（或者说是在度数为 $1$ 的点
- 距离树上一个点最远的点一定是任意一条直径的一个端点
- 两个联通块的并的直径是各自的联通块的两条直径和两对端点分别组合形成的四个路径共六个路径中的某一个
算法
从任一点 $x$ 开始 $bfs$ 找到距离该点最远的点 $u$，然后从 $u$ 再次进行 $bfs$，找到距离 $u$ 最远的点 $v$，$u$ 到 $v$ 的路径就是直径，该方法不适用于边权不为 $1$ 的情况（指的是 $bfs$，如果还是两次找最远的点的话是没问题的
树形 $dp$，同样适用于边权不为 $1$ 的情况
1
2
3
4
5
6
7
8
9int f[maxn], ans;
void dfs(int u, int fa) {
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to, w = e[i].w; if (v == fa) continue ;
dfs(v, u); ans = max(ans, f[u] + f[v] + w);
f[u] = max(f[u], f[v] + w);
}
}
例题
简要题意：现在有 $n$ 个点，同时有 $m$ 次操作，操作有两种，第一种操作给定两个点 $x,y$，加入一条连接 $x$ 和 $y$ 的边，保证加入边之后仍然是森林；第二种操作给定一个点 $x$，问 $x$ 所在的联通块内与它距离最远的点的距离
$n\le 3\times 10^5,m\le 5\times 10^5$，强制在线
简要题解：首先根据直径的性质，我们知道距离一个点最远的点一定是任意一条直径的两个端点中的某一个端点，所以我们只需要在有加边的情况下动态维护直径，同时根据直径的性质，两个两个联通块的并的直径是各自的联通块的两条直径和两对端点分别组合形成的四个路径共六个路径中的某一个，那么现在我们还需要支持动态加边，求树上两点的距离，这个东西只能用 $LCT$ 来维护，所以我们用 $LCT$ 来维护距离，用并查集维护直径即可
时间复杂度 $O(n\log n)$
树 hash
判断子树同构
给出一种保证不会错的方法
1 | void dfs(int u) { |
时间复杂度为 $O(n\log n)$
判断有根树同构
一种类似集合 $hash$ 的方法
1 | ull dfs(int u, int fa) { |
判断无根树同构
我们以重心为根进行 $hash$，注意因为重心可能有两个
例题
树上的信息维护方法
在 $dfs$ 的同时维护每个点的子树内的信息
这个有两种方法，第一种是 $dsu~on~tree$
第二种比较 $trick$，我们在进入这个点的时候减掉需要查询的信息，然后离开的时候再加上
在 $dfs$ 的同时维护根到当前点的信息
这个比较简单，进入一个点加入，离开一个点删除即可
树上的经典问题
给出 $n$ 个点的树和 $k$，将树划分成 $\frac{n}{k}$ 个连通块，且每个连通块的点数都是 $k$ 的方案数是唯一的
树上多点的集合点
定义：大概就是给你树上的若干个点，求在树上选择一个集合点使得这些点到集合点的距离的和最小
几个结论和方法：
- 两个点的话一定选择 $lca$
- 三个点的集合点是三点的三个 $lca$ 中深度最大的那个，另外两个 $lca$ 相同且深度较小
- 三个点的总距离为两两之间的距离除以 $2$
到树上多点距离相同且最小的点
简要题意：给定一棵 $n$ 个点的树，现在有 $m$ 次询问，每次询问给定 $k$ 个点，求是否存在一个到这 $k$ 点的距离相等的点，如果有多个点求距离最小的那个
$n\le 10^6,\sum k\le 10^6$
简要题解：不妨假设存在这么一个点 $x$ 且距离为 $d$，我们以 $x$ 为根，容易在给定点集中一定有两个点的距离为 $2\times d$
那么我们直接把这个路径中点拿出来判断即可，至于如何求点集中最远点对，显然其中一个点是深度最大的点，时间复杂度 $O(n\log n )$
树上路径求交
时间复杂度瓶颈在于求 $lca$，如果求 $lca$ 能做到 $O(1)$，那么时间复杂度为 $O(1)$
1
2
3
4
5
6
7inline pair<int, int> merge(pair<int, int> u, pair<int, int> v) {
auto [a, b] = u; auto [c, d] = v;
int t[] = {LCA::get(a, c), LCA::get(a, d), LCA::get(b, c), LCA::get(b, d)}; sort(t, t + 4, cmp);
if (t[0] != t[1] || dep[t[0]] == max(dep[LCA::get(a, b)], dep[LCA::get(c, d)]))
return make_pair(t[0], t[1]);
else return make_pair(-1, -1);
}判断点是否在树上某路径上
时间复杂度瓶颈在于求 $lca$，如果求 $lca$ 能做到 $O(1)$，那么时间复杂度为 $O(1)$
1
2
3
4
5
6inline bool check(pair<int, int> path, int x) {
auto [u, v] = path; int lca = LCA::get(u, v);
if (LCA::get(lca, x) != lca) return false;
if (LCA::get(u, x) != x && LCA::get(v, x) != x) return false;
return true;
}简要题意：给定一棵 $n$ 个节点的无根树，每个节点有一个颜色 $c_i$，现在有 $m$ 次询问，每次询问给定 $x,y,z$，问从 $x$ 到 $y$ 的简单路径上是否有颜色 $z$
$n,m\le 10^5$
简要题解：我们考虑在 $dfs$ 的过程中维护当前节点到根的路径上每种颜色的深度最深的出现位置，那么对于一次询问，如果对于 $x$ 节点到根路径上 $z$ 出现的位置与 $y$ 到根路径上 $z$ 出现的位置相同，那么除非这个位置是 $x$ 和 $y$ 的 $lca$，否则说明 $z$ 没有出现在 $x$ 到 $y$ 的简单路径上，出现位置不同则说明 $z$ 一定出现在 $x$ 到 $y$ 的简单路径上
但是求 $lca$ 太麻烦了，所以我们在 $dfs$ 的时候把颜色放到儿子节点上，这样就不用特判 $lca$ 了，时间复杂度 $O(n)$
一棵 $n$ 个节点的树，边有边权。
每个点可能是关键点，每次操作改变一个点是否是关键点。
求所有关键点形成的极小连通子树的边权和的两倍
直接按照 $dfs$ 序排好之后两两求 $lca$ 即可
一棵树，相邻点异色，每次可以改变同色连通块的颜色，求最少多少次操作将树上的节点都变成一个颜色
结论：需要的最少操作次数为 $\lceil\frac{d}{2}\rceil$，其中 $d$ 是这棵树的直径
求从所有点出发的最长路
我们利用 $up\underline{}down$，但需要注意最值不能减，所以我们额外记录一个次大值，需要注意对于一个点只从每个儿子中取一个最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23int f[maxn], g[maxn], fr[maxn];
void dfs(int u, int fa) {
f[u] = g[u] = -1;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to, w = 1; if (v == fa) continue;
dfs(v, u);
if (f[u] < f[v] + w) g[u] = f[u], f[u] = f[v] + w, fr[u] = v;
else if (g[u] < f[v] + w) g[u] = f[v] + w;
}
if (f[u] < 0) f[u] = 0, fr[u] = u;
else if (g[u] < 0) g[u] = 0;
}
void Dfs(int u, int fa) {
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to, w = 1, t; if (v == fa) continue;
if (fr[u] == v) t = g[u] + w;
else t = f[u] + w;
if (f[v] < t) g[v] = f[v], f[v] = t, fr[v] = u;
else if (g[v] < t) g[v] = t;
Dfs(v, u);
}
}求从所有点出发到其它所有点的路径和
同样我们使用 $up\underline{}down$
在树上选取若干条边，需要保证加入这些边后没有一个点的度超过 $k$，求最大边权和
对于儿子，我们只需要知道儿子还能不能选一次，所以我们令 $f[u]$ 表示还能选，$g[u]$ 表示不能选
然后做树形 $dp$，细节详见代码
在树上选一条点个数小于等于k的简单路径，使路径外的点到路径的距离的最大值最小
能够发现这条路径一定是在直径上，所以我们可以考虑在直径上做一个滑动窗口
但是这样太麻烦了，我们考虑用类似拓扑排序东西来做一个贪心
即从叶子开始删点，并更新每个点向子树内拓展的最大距离，直到删的只剩 $k$ 个点且为一条链
给定义一棵树，可以从任意一个点开始进行 $dfs$，求后根遍历的最小字典序解
简要题意：简要题意：给定义一棵 $n$ 个点的树，可以从任意一个点开始 $dfs$，求后根遍历的最小可能字典序
$n < 2\times 10^5$
简要题解：容易发现，后根遍历的第一个点一定是最小的叶子 $v$，那么接下来我们只能返回到 $v$ 的父亲 $u$，对于 $u$，我们有两种抉择，一种是认为 $u$ 是我们所选定的根，那么我们会将 $u$ 的除 $v$ 以外的子树按照最小叶子排序依次 $dfs$，最终将 $u$ 加入答案；或者认为 $u$ 还有父亲，那么我们会将 $u$ 的除 $v$ 以外的子树按照最小叶子排序，不妨假设有 $k$ 个子树，先依次 $dfs$ 前 $k - 1$ 个，然后将 $u$ 加入答案，然后 $dfs$ 最后一个子树
至于实现，我们以最小的叶子为根建树，这样方便得到每个子树的最小叶子，同时在 $dfs$ 的时候，我们记录现在是在向上还是向下
2021 ICPC Southeastern Europe Regional Contest K Amazing Tree
简要题意：给定一棵 $n$ 个节点的树，每个点有一个颜色 $c_i$，令 $d(i,j)$ 表示 $i$ 到 $j$ 的简单路径上的颜色种数， 令 $f_i=\sum_{j=1}^nd(i,j)$，求所有的 $f_i$
$n,c_i\le 10^5$
简要题解：首先我们考虑一种可以求根节点的答案的方法，大概就是维护 $sum_c$ 表示 $c$ 这个颜色贡献，做法如下：
1
2
3
4
5
6
7
8void dfs(int u, int fa) {
int tmp = sum[c[u]]; sz[u] = 1;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
dfs(v, u); sz[u] += sz[v];
}
sum[c[u]] = sz[u] + tmp;
}容易得到 $f_{rt}=\sum sum_c$，我们考虑换根来求其他点的 $f$，容易发现从 $u$ 换到其儿子 $v$ 时，只有 $c_u$ 和 $c_v$ 这两种颜色的贡献会发生变化，具体的，$c_v$ 的贡献会变成 $n$，相当于在之前的基础上减掉以$u$ 为根时除 $v$ 的以外的其他子树内 $c_v$ 的贡献，$c_u$ 的贡献首先应该减去 $sz_v$， 同时要加上 $v$ 的子树内不考虑 $u$ 时 $c_u$ 这个颜色的贡献
对于后者容易发现我们上面那个朴素做法的 $sum$ 与这个东西类似， 我们令其为 $a_v$
1
2
3
4
5
6
7
8
9
10
11void dfs(int u, int fa) {
int tmp = sum[c[u]];
sum[c[fa]] = 0; sz[u] = 1;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
dfs(v, u); sz[u] += sz[v];
}
sum[c[u]] = sz[u];
a[u] = sum[c[fa]];
sum[c[u]] += tmp;
}对于前者，我们直接在换根的时候，同时维护 $sum_c$ 表示以当前点为根 $c$ 的贡献，换根的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12void Dfs(int u, int fa) {
int tmp1 = sum[c[u]], tmp2 = sum[c[fa]];
if (u != 1) {
f[u] = f[fa] - sz[u] + a[u] + n - sum[c[u]];
sum[c[u]] = n; sum[c[fa]] = n - sz[u] + a[u];
}
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
Dfs(v, u);
}
sum[c[u]] = tmp1; sum[c[fa]] = tmp2;
}