简单的还有吓人的树论
24 年的 Ice_lift 和 26 年的 Ice_lift 的笔记的整合,可能还不够完善后续还会继续更新。难的可能并不难,但是简单的确实挺简单的,笔者本质很菜。
使用了 Deepseek 进行了部分段落公式规范化,保证人类贡献大于 AI。
1 最近公共祖先 - \text{LCA}
定义:最近公共祖先简称
性质:
- 两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先
\text{LCA}(A\cup B)=\text{LCA}(\text{LCA}(A), \text{LCA}(B)) 。 -
- 两点的最近公共祖先必定处在树上两点间的最短路上,且为两点间最短路上的拐点。
1.0 常用算法
-
暴力跳树法 将
(u, v) 中深度较深的点不断向上跳直到\text{dep}_{u'} = \text{dep}_v ,接着再同时向上直到u' = v' ,此时\text{LCA}(u,v) = u' 。优势:在随机树中较为优秀,好写。
劣势:复杂度较高。
复杂度:
O(\max_u \text{dep}_u) 。 -
倍增跳树法 暴力法的一步一步跳太慢了,不妨考虑每次跳
2^k 步,这样效率会优化到O(\log n) 。每次跳
2^k 步,需要预处理出任意点的2^i 级祖先。祖先关系显然是可合并信息,所以f_{i,k}=f_{f_{i,k-1},k-1} 。预处理时间复杂度:O(n \log n) 。优势:好写,且可以同时处理两点路径上其他可合并信息。
劣势:常数较大。
复杂度:
O(n \log n) \sim O(\log n) 。 -
染色法 对于
(u, v) ,将其中一点到根的路径染色,\text{LCA}(u, v) 为另一点到根路径上第一个被染色的节点。小推论:记
\text{cnt}_v 为另一点到根路径上被染色的节点数量,则\text{dep}_{\text{LCA}(u,v)} = \text{cnt}_v 。优势:可以联系树剖进行快速计算
\text{dep}_{\text{LCA}} 。劣势:复杂度较高。
复杂度:
O(\max_u \text{dep}_u) 。 -
重链剖分法
前置知识:树链剖分 - OI Wiki。
下称跳链为从一点到其链头的父亲节点。
我们发现当
(u, v) 两点不断进行跳链操作,直到两点所在链相同时,深度较小的点为\text{LCA} 。证明:
每次跳链操作并不会使得两点经过同样的边(每条边仅属于一条链,在两点所在链相同时经过的边一定不同),所以当两点所在链相同时,形成的路径一定为简单路径,又因为树上两点简单路径有且仅有一条,所以这条路径一定为最短路径,而
\text{LCA}(u, v) 为(u, v) 最短路上的拐点,当两点所在链相同时,深度较浅节点为(u, v) 路径上拐点,所以该点为\text{LCA}(u, v) 。由于一个点到根节点至多经过
O(\log n) 条重链,所以单次查询时间复杂度O(\log n) 。优势:常数小,方便快捷,易拓展。
劣势:查询还不够快,可以卡满
\log 。复杂度:
O(n) \sim O(\log n) 。 -
欧拉序 + RMQ 法
欧拉序指 dfs 过程中到达或回溯到一个节点就记录的一种序列。
我们记
\text{fst}_u 表示u 第一次在 dfs 序中出现的下标,不妨设\text{fst}_u < \text{fst}_v 。**优势**:该做法可以做到 $O(1)$ $\text{LCA}$,某些需要多次查询两点 $\text{LCA}$ 的题目里无可替代。 **劣势**:预处理常数较大,在 NKOJ 上不如树剖。 **复杂度**:$O(n \log n)$ 预处理,$O(1)$ 查询。
1.1 应用
1.1.1 树上差分
对于一颗树进行树上链进行可差分操作且询问在操作之后的问题可以用树上差分求解。
联系序列差分,区间修相当于将
不妨假设对于一个点的最后的增量为
记根为
此时我们实现了对于一个点到根节点的路径上所有点的修改操作。
那么怎么实现两点间的路径操作?
考虑容斥,我们先对于
如果对于边进行可差分操作,可以将边转化到两个端点中深度较深的点上,然后同点操作一样,不过此时
【例题】
-
P6869 [COCI2019-2020#5] Putovanje
给你一棵有
n 个点的树,节点编号从1 到n 。经过树上的边需要收费。第
i 条边有单程票(只能用一次)价格c_{i1} 和多程票(可以用无限次)价格c_{i2} 。你在访问途中可能会重复走一条边,所以多程票有时更划算。请你求出从
1 依次访问到n 最少需要多少费用。由于树上路径唯一,所以
1 依次到n 的路径固定,可以统计每条边经过了多少次,最终代价为\sum \min(c_{i1} \times \text{cnt}_i, c_{i2}) 。统计每条边经过了多少次就可以用树上差分将
i \to i + 1 的路径上的边\text{cnt} \gets \text{cnt} + 1 。
2 dfs 序
dfs 序指对树进行 dfs 时的访问顺序,OI 中存在几种定义不同的 dfs 序,其性质和作用效果也不相同。
2.1 朴素 dfs 序
仅在 dfs 进入节点时加入序列。
void dfs (int u) {
dfn[u] = ++ idx;
for (int v : g[u]) dfs(v);
}
有以下性质:
- 子树在 dfs 序上呈一段连续区间,
u 子树内所有点在 dfs 序上对应[\text{dfn}_u,\ \text{dfn}_u + \text{siz}_u - 1] 。 - 一个节点的祖先节点的 dfs 序一定小于该点 dfs 序。
- 若
\text{dfn}_u < \text{dfn}_v ,则要么u 是v 的祖先,要么\text{subtree}(u) 整体排在\text{subtree}(v) 之前——子树区间是嵌套或相离的,绝不交叉。
2.1.1 序列化
把
2.1.2 换根
把根换成
2.2 括号序
在进入节点和退出节点的时候都记录:
void dfs(int u) {
in[u] = ++idx;
for (int v : g[u]) dfs(v);
out[u] = ++idx;
}
性质:
-
- 区间内出现奇数次的点恰好是路径点集。设
\text{in}_u < \text{in}_v :- 若
u 是v 的祖先(即\text{LCA}(u, v) = u ):路径点集= [\text{in}_u, \text{in}_v] 中出现奇数次的点; - 否则:取区间
[\text{out}_u, \text{in}_v] ,路径点集= 该区间内出现奇数次的点\cup\ \{u\} 。此时\text{LCA}(u, v) 在区间内出现0 次,需要单独补上。
- 若
2.2.1 树上莫队
拍成括号序后,路径询问变成序列上的区间询问,直接套莫队:维护
void add (int p) {
int u = dfn[p];
if (!vis[u]) { if (!cnt[c[u]] ++) ans ++; }
else { if (!-- cnt[c[u]]) ans --; }
vis[u] ^= 1;
}
【例题】
- SP10707 COT2 - Count on a tree II
2.2.2 路径和问题
在
- 若
u 是v 的祖先:\sum_{i = \text{in}_u}^{\text{in}_v} w_i 就是路径u \leftrightsquigarrow v 的点权和; - 否则:
\sum_{i = \text{out}_u}^{\text{in}_v} w_i 等于路径u \leftrightsquigarrow v 的点权和再减去a_{\text{LCA}(u, v)} 。
子树整体加
2.3 欧拉序
在进入节点和回溯到节点时记录。
void dfs (int u) {
dfn[++ idx] = u, fst[u] = idx;
for (int v : g[u]) {
dfs(v);
dfn[++ idx] = u;
}
}
序列长度为
性质(其中
-
- 因为
\text{LCA}(u, v) 在区间内至少出现一次,所以“取最小深度”一定取得到它。
这正是 3.1.0 中“括号序 + RMQ”法的依据:把欧拉序上的深度建成 ST 表,即可
:::info[Code]
int mi[N << 1][20], dep[N], log_2[N << 1];
int pos[N << 1][20];
vector<pi> g[N];
void dfs0 (int u, int fa) {
dfn[fst[u] = ++ idx] = u, mi[idx][0] = dep[u] = dep[fa] + 1;
for (auto [v, w] : g[u])
if (v != fa) {
dis[v] = dis[u] + w;
dfs0(v, u);
dfn[++ idx] = u, mi[idx][0] = dep[u];
}
}
void build () {
dfs0(1, 0);
for(int i = 1; i <= idx; i ++) pos[i][0]=i;
for(int i = 2; i <= idx; i ++) log_2[i] = log_2[i >> 1] + 1;
for(int k = 1; k <= 20; k ++)
for(int i = 1; i + (1 << k) - 1 <= idx; i ++){
int x = mi[i][k - 1], y = mi[i + (1 << k - 1)][k - 1];
if(x < y) mi[i][k] = x, pos[i][k] = pos[i][k-1];
else mi[i][k] = y, pos[i][k] = pos[i + (1 << k - 1)][k - 1];
}
}
int lca(int l,int r){
int _ = log_2[r - l + 1];
return mi[l][_] < mi[r - (1 << _) + 1][_] ? pos[l][_] : pos[r - (1 << _) + 1][_];
}
:::
优势:
劣势:预处理常数大。
复杂度:
相关其他应用:欧拉环游树,详见动态树部分。
3 \text{dfn} 排序与虚树
给定关键点集
-
引理 1:设
S=\{a_1,a_2,\dots,a_k\} ,则\text{LCA}(S)=\text{LCA}\left(\arg\min_{u\in S} \text{dfn}_u,\ \arg\max_{u\in S} \text{dfn}_u\right) -
引理 2:设
\text{rt} 为根,S 中的点按\text{dfn} 升序为b_1,b_2,\dots,b_k ,令b_{k+1}=b_1 ,则\text{ans}=\sum_{u\in S}\text{dis}(u,\text{rt})-\sum_{i=1}^{k}\text{dis}(\text{LCA}(b_i,b_{i+1}),\text{rt})-\text{dis}(\text{LCA}(S),\text{rt}) 同理也可以如此维护虚树大小。
-
引理 3:虚树的点集恰为
S \cup \{\text{LCA}(b_i, b_{i + 1}) : 1 \le i < k\} ,所有分叉点都在这个集合里。
3.1 单调栈建虚树
按
sort(a + 1, a + k + 1, [](int x, int y) { return dfn[x] < dfn[y]; });
k = unique(a + 1, a + k + 1) - a - 1;
st[top = 1] = 1;
for (int i = 1; i <= k; i ++) {
int u = a[i];
if (u == st[top]) continue;
int l = lca(u, st[top]);
while (top > 1 && dep[st[top - 1]] >= dep[l])
add(st[top - 1], st[top]), top --;
if (st[top] != l) add(l, st[top]), st[top] = l;
st[++ top] = u;
}
while (top > 1) add(st[top - 1], st[top]), top --;
3.2 动态点集
引理 2 可以动态维护:用 set(以
插入 / 删除
ans += dis[x] + dis[lca(l, r)] - dis[lca(x, l)] - dis[lca(x, r)];
于是虚树边权和可以
同样的,这个过程也可以使用以
在一些题目中,用线段树合并维护会比 set + 启发式合并更优秀。
【例题】
-
P3320 [SDOI2015] 寻宝游戏
维护虚树边权和,用线段树做法就可以。
:::info[Code]
#include <bits/stdc++.h> using namespace std; // #define int long long #ifdef ONLINE_JUDGE char buf[1 << 23] , * p1 = buf , * p2 = buf , obuf[1 << 23] , * O = obuf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) #endif inline int read() { int x = 0 , f = 1;char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1;ch = getchar(); } while (isdigit(ch)) x = x * 10 + (ch ^ 48) , ch = getchar(); return x * f; } #define endl '\n' typedef long long ll; typedef pair<int, int> pi; const int N = 1e5 + 10; int n, m; ll dis[N]; int dfn[N<<1], idx, fst[N]; int mi[N<<1][20], dep[N],log_2[N<<1]; int pos[N<<1][20]; vector<pi> g[N]; void dfs0 (int u, int fa) { // cout <<dis[u]<<endl; dfn[fst[u]=++idx]=u, mi[idx][0] = dep[u] = dep[fa] + 1; for (auto [v, w] : g[u]) if (v != fa) { dis[v]=dis[u]+w; dfs0(v, u); dfn[++ idx] = u, mi[idx][0] = dep[u]; } } // 预处理 LCA void build () { dfs0(1,0); for(int i=1;i<=idx;i++)pos[i][0]=i; for(int i=2;i<=idx;i++)log_2[i]=log_2[i>>1]+1; for(int k=1;k<=20;k++) for(int i=1;i+(1<<k)-1<=idx;i++){ int x=mi[i][k-1],y=mi[i+(1<<k-1)][k-1]; if(x<y)mi[i][k]=x,pos[i][k]=pos[i][k-1]; else mi[i][k]=y,pos[i][k]=pos[i+(1<<k-1)][k-1]; } } int lca(int l,int r){ int _=log_2[r-l+1]; return mi[l][_]<mi[r-(1<<_)+1][_]?pos[l][_]:pos[r-(1<<_)+1][_]; } struct node { int L, R; ll res; }t[N<<2]; int cnt[N<<2]; int ls[N<<2], rs[N<<2], tot; // 合并路径和 node operator + (node x, node y) { if (!y.L) return x; if (!x.L) return y; ll tmp = dis[dfn[lca(x.R, y.L)]]; return {x.L, y.R, x.res + y.res - tmp}; } void upd (int &p, int l, int r, int x, int v) { if (!p) p = ++ tot; if (l == r) { cnt[p] += v; if (cnt[p] > 0) t[p] = {x, x, dis[dfn[x]]}; else t[p] = {0, 0, 0}; } else { int mid=l+r>>1; if(mid>=x)upd(ls[p],l,mid,x, v); else upd(rs[p],mid+1,r,x,v); if (ls[p] && rs[p]) t[p]=t[ls[p]]+t[rs[p]]; else if (ls[p]) t[p] = t[ls[p]]; else t[p] = t[rs[p]]; } } bool vis[N]; signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>n>>m; for(int i=1,u,v,w;i<n;i++){ cin>>u>>v>>w; g[u].emplace_back(v,w); g[v].emplace_back(u,w); } build(); int rt=0; while (m --) { int x; cin >> x; upd(rt, 1, idx, fst[x], vis[x] ? -1 : 1); vis[x] ^= 1; cout << (t[rt].res - dis[dfn[lca(t[rt].L, t[rt].R)]]) * 2 << endl; } return 0; }:::
-
P5327 [ZJOI2019] 语言
对于每个点,其合法点集构成一个连通块,类似的,离线后扫描整个树维护每个点对应的虚树大小即可,线段树合并可以做到
O(n \log n) 。
4 重链剖分
如果 dfs 时先走重儿子,那么同一个
- 子树连续:
\text{subtree}(u) 对应[\text{dfn}_u,\ \text{dfn}_u + \text{siz}_u - 1] ; - 重链连续,且链头的
\text{dfn} 最小:链\text{top} \leftrightsquigarrow u 上的点对应[\text{dfn}_{\text{top}},\ \text{dfn}_u] 。
由重链上区间连续 + 点到根路径至多经过
实现上形如:
void sol (int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
work on [dfn[top[u]], dfn[u]];
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
work on [dfn[v], dfn[u]];
}
【例题】
- P3384 【模板】重链剖分 / 树链剖分
- P3178 [HAOI2015] 树上操作
5 特殊树上信息
5.1 重心
定义:以
性质:
- 树中所有结点到某个结点的距离和中,到结点
c 的距离和最小。 - 以树中所有结点为根时,真子树的大小的最大值中,结点
c 的最大真子树最小。 - 一棵树的重心数量只能是
1 / 2 ,特别的,如果有两个重心,一定是相邻的两个点。而且删去它们的连边后,树将变为两个大小相同的连通分量。 - 在一棵树上添加或删除一个叶子,那么它的重心最多只移动一条边的距离。
- 把两棵树通过一条边相连得到一棵新的树,那么新树的重心在连接原来两棵树的重心的路径上。
求法:
可以通过一次 dfs 维护以
应用:点分治。
【例题】
-
CF1827D Two Centroids
当重心个数为
2 时,两侧连通块大小相等。等价于我们要调整成两个相等的连通块。考虑当前重心c ,等价于选择一个相邻点v 让其作为新的重心,给v 子树加点使得\text{siz}_v = n - \text{siz}_v ,也就是要增加n - 2\text{siz}_v 。这里当v 是c 的最大子树时答案最小。于是问题变成我们如何动态维护重心及其最大子树大小
s 。如果新加的点在
c 的最大子树内,且\text{siz}' > \frac{n}{2} ,则c 会向最大子树对应的儿子移动。如果移动了,那么
s 必定等于\frac{n}{2} ,否则s \gets \max(s, \text{siz}'_v) 。这里只需要动态维护对应子树大小即可,用 3.2.1.2 的技巧和树状数组加点即可做到。
实现上,先将完整的树求出来,
c 的最大子树对应儿子在以1 为根的树上可能为其父亲或者是子节点。为父亲时可以直接移动,为子节点时要从新点倍增找到对应的儿子。
5.1.1 动态带权重心
比上面例题的做法更通用普遍。很厉害的东西。
每个点有一个权重
a_i ,找到使得\sum_{u = 1}^{n} a_u \times \text{dis}(u, v) 最小的v ,即带权重心。
以下默认
随便钦定一个点为根,记
和普通重心一样,其判定条件等价于删除该点后剩余的连通分量的权值和均
可以用调整法理解这个东西,记到某个点的带权路径总为
考虑
重心是满足
因为其最深,所以该点的儿子满足
2S_v < T ,同时该点满足2S_u \ge T ,符合上面所述的判定条件。
这里用到了一个很巧妙的东西,如果我们知道实际重心子树内的任意一点
引理:若
用线段树二分找到中位数后倍增就可以找到实际重心了。
采用线段树在 dfs 序上维护的话,这里每次查询
【例题】
-
QOJ#3307 树上查询 17
链修改点权,子树修改点权,然后动态查询重心,就是模板题,但是这里要求距离根最近的所以在多个重心的情况下要特判倍增找出来的点的祖先是否也满足条件。
-
P3345 [ZJOI2015] 幻想乡战略游戏
这题带边权,但是其实差异不大,因为边权为正,仍然用调整法理解,相当于给增量乘了一个正系数,重心判定条件不变。难点在于我们该如何快速求出
F(\text{rt}) 。考虑对
F(u) 拆贡献:\begin{array}{l} F(u) = \sum a_v \times \text{dis}(v, u) \\ = \sum a_v \times (\text{dis}(v) + \text{dis}(u) - 2 \times \text{dis}(\text{LCA}(u,v))) \\ = \sum a_v \times \text{dis}(v) + \sum a_v \times \text{dis}(u) - 2\sum a_v \times \text{dis}(\text{LCA}(u, v)) \\ = B + A \times \text{dis}(u) - 2G(u) \end{array} 前两个都是定值,对于
G(u) = \sum a_v \times \text{dis}(\text{LCA}(u, v)) ,按边拆贡献:G(u) = \sum_{c \in \text{path}(u \leftrightsquigarrow \text{rt})} w_c \times S_c 记
w_c = w(c, \text{fa}_c) ,表示c 到父亲的边的边权(w_{\text{rt}} 视作0 )。因为一条边当u, v 都属于\text{subtree}(c) 时会贡献a_v \times w_c ,对a_v 求和等价于S_c 。那么修改
a_i \gets a_i + e 对G(u) 的影响即为e \sum w_c ,可以用重链剖分 + 线段树维护一条链上的\sum w_c 和\sum w_c \times S_c 。对A, B 的影响都是可以直接O(1) 计算的。5.2 直径
定义:树上所有路径中,最长的路径即为直径。
下面记直径两个端点为
性质:
- 边权非负时,对于任意点
u ,\max \text{dis}(u, v) 一定是\max(\text{dis}(u, l_1), \text{dis}(u, l_2)) 。 - 用一条边合并两个树时,新直径的端点一定来源于原两棵树直径对应四个端点。
- 所有直径都经过树中心。
求法:
- 如果边权全正则考虑两次 dfs,第一次从任意点出发找到最远点,然后以该最远点出发再次找到最远点。由性质 1,第一次找到的点一定是直径端点之一,第二次则找到另一个直径端点。
- 树形 DP,记
f_u 表示从u 出发到u 子树内的点的最长路径长度,考虑类似换根地维护从u 出发到\text{subtree}(u) 外任意点的最长距离g_u ,直径长度为\max (f_u + g_u) 。 - 还是树形 DP,维护
f_u 表示u 到子树内任意点的最长距离,在更新f_u \gets \max(f_u, f_v + w(u, v)) 前维护\text{ans} \gets \max(\text{ans}, f_u + f_v + w(u, v)) 。
【例题】
-
Gym-104976F Top Cluster
我们知道在边权非负的情况下直径可以合并,于是可以放到线段树上,按照值域维护当前值域范围内的点之间的直径,又因为
\max \text{dis}(u, v) 一定是\max(\text{dis}(u, l_1), \text{dis}(u, l_2)) ,可以快速查询一个点到给定点集的最远距离。而\text{mex} 具有可二分性,在线段树上二分找到第一个最远距离\le k 的位置即可。ll calc(int u,int v){ return dis[u]+dis[v]-2ll*dis[lca(fst[u],fst[v])]; } struct node{ int u[2]; ll len; }t[N<<2]; node operator+(node x,node y){ if(!x.u[0])return y; if(!y.u[0])return x; node res={{0,0},0}; ll tmp; if((tmp = calc(x.u[0],y.u[0]))>res.len) res.u[0]=x.u[0],res.u[1]=y.u[0],res.len=tmp; if((tmp = calc(x.u[0],y.u[1]))>res.len) res.u[0]=x.u[0],res.u[1]=y.u[1],res.len=tmp; if((tmp = calc(x.u[1],y.u[0]))>res.len) res.u[0]=x.u[1],res.u[1]=y.u[0],res.len=tmp; if((tmp = calc(x.u[1],y.u[1]))>res.len) res.u[0]=x.u[1],res.u[1]=y.u[1],res.len=tmp; if(x.len>res.len) res=x; if(y.len>res.len) res=y; return res; }
5.2.1 动态维护带权直径
一种很蠢的做法是使用第二种 DP 状态直接 DDP,码量大的同时复杂度也很劣,我写的是
下面讲解一种很快很便捷的东西(但是只适用于正边权)。
我们回归直径本身的定义,相当于要找到
把它放到欧拉序上,等价于:
由于外部取
为什么只适用于正边权:
\text{LCA} 是欧拉序区间内深度最小的点,如果有负权边则\text{dis} 关于\text{dep} 不具有单调性了,\text{dis} 最小的点深度不一定最小,也就不一定是\text{LCA} 。
这样就脱离树结构本身了,这是可以用线段树维护的东西。
对于一个区间我们维护五个信息:ma, mi, l, r, ans。
ma:区间最大值mi:区间最小值l:\text{dis}(i) - 2\text{dis}(j) 的最大值r:-2\text{dis}(j) + \text{dis}(k) 的最大值ans:\text{dis}(i) - 2\text{dis}(j) + \text{dis}(k) 的最大值
考虑合并两个区间的信息:
然后放到线段树上维护就可以了,修改一条边的边权对
值得注意的是,如果维护的是动态“加边”的情形,等价于没有加入的边的端点不能作为
特别的,如果有负边权,考虑使用点分树维护。具体怎么做先咕了。
【例题】
-
QOJ#9416 Intersection of Paths
对边拆贡献,一个查询的
k 等价于只有断开该边后形成的两个连通块大小均\ge k 才能贡献。然后求满足条件的边构成的路径的最长长度,也就是直径。满足条件的边必然构成连通块,因为我们的修改是独立的所以可以离线按照
k 从大到小处理询问,同时对边排序,就变成了按序激活边的过程。使用上面所述的方法维护即可。