图论

树

LCA

性质

1. \(LCA(A \cup B) = LCA(LCA(A), LCA(B))\)
2. 一堆点集的LCA 等于其中 dfn 最大的和最小的点的 LCA

dfs序求lca

好写且 \(O(1)\)，吊打欧拉序和倍增。

如果两个点 \(x\) 和 \(y\) 不存在祖孙关系，那么 \(LCA(x,y) = fa(min(dfn_x, dfn_y))\)。

我们钦定 \(dfn_x < dfn_y\) 这里的 min() 是指 \([dfn_x, dfn_y]\) 之间深度最小的点的编号。

考虑证明很简单，思考dfn是怎么来的即可。

如果存在祖孙关系，那么 \(LCA = x\)，但是为了方便写，我们可以把两种情况统一起来，我们将dfn_x加一即可，这样加一之后不影响第一种情况，第二种情况的答案也可以算到。

代码：

int dfn[N], tim, st[21][N];
void dfs(int u, int pre) {
	st[0][dfn[u] = ++tim] = pre;
	for(int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if(v == pre) continue;
		dfs(v, u);
	}
}
int Min(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
void init() {
	for(int i = 1; i <= 20; i++) 
		for(int j = 1; j + (1 << i) - 1 <= n; j++) 
			st[i][j] = Min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
int lca(int x, int y) {
	if(x == y) return x;
	if((x = dfn[x]) > (y = dfn[y])) swap(x, y);
	int d = 31 ^ __builtin_clz(y - x); x++;
	return Min(st[d][x], st[d][y - (1 << d) + 1]);
}

实际实现不需要dep和fa数组，具体细节见代码。

这个做法的瓶颈在RMQ，如果用一些高科技搞RMQ可以做到 \(O(n)~O(1)\)，但基本常数较大且不怎么好些。

树剖求lca

\(O(n)~O(logn)\) 常数小，代码也比较简单，可以替代倍增，但最好的还是dfs序。

树的直径

两种方法：两次dfs或者树形DP。推荐第二种，因为好写且支持找负边权的直径，树形DP又有两种方法，这里写一种好写的。

不过有意义的，两次dfs的结论也可以记住：

在都是非负边权的情况下，从树上任意一点 \(x\) 出发，到达的最远的点 \(y\) 一定是直径的一端。

具体证明很简单，使用反证法，分三种情况分别考虑

1. \(x\) 就在直径上
2. \(x\) 不在直径上，但是求得的路径 \((a,b)\) 与直径 \((z, w)\) 有交点。
3. 没有交点。

DP代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, dp[N], ans;
void chmx(int &x, int y) { x = max(x, y); }
vector<int> G[N];
void dfs(int u, int fa) {
	for(int v : G[u]) if(v ^ fa) {
		dfs(v, u);
		chmx(ans, dp[u] + 1 + dp[v]);
		chmx(dp[u], 1 + dp[v]);
	}
}
int main() {
	scanf("%d", &n);
	for(int i = 1, u, v; i < n; i++)
		scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
	dfs(1, 0);
	printf("%d", ans);
	return 0;
}

树的重心

性质

1. 重心最多两个，如果有两个，那么肯定相邻。
2. 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。（这个也是充要条件）
3. 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。（这个性质也挺好）
4. 要是通过一条边把两棵树连起来，那么新的重心在原来两棵树的重心的路径上。（有助于动态维护重心）
5. 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离

证明： 先咕着。

树剖

长剖和实剖先不展开。主要就是重链剖分。
重链剖分及其擅长解决树上路径问题，他把树剖成了若干条重链，并且任意一条路径上最多 \(logn\) 条重链，这使得我们可以使用一些可以维护链上信息并且支持信息快速合并的数据结构来维护重链，并且树剖利用和拓展dfs序的性质，把链搞成一个区间，使得我们的维护更加的方便。
顺带着dfs序的性质，树剖对于子树信息的维护也很擅长。
具体算法内容就不赘述了，这里只做总结。

dsu on tree

也叫树上启发式合并，有些时候我们完全可以直接启发式合并，但是这个算法给了另一种启发式合并的思路，dsu on tree主要是对子树信息统计，具体算法很人类智慧，考虑我们要统计每个点的子树信息，并且只能用一个桶或者数据结构。

比如我们dfs目前到了节点 \(u\)，我们会将 \(u\) 的儿子 \(v\) 一一递归下去，这样的话我们遍历完一个儿子就要清空桶，不然其他儿子的信息就不对，遍历完儿子之后我们再来统计 \(u\) 的信息，那么就有一个人类智慧，最后一个儿子遍历完不用清空，可以留下来给 \(u\) 用，这样就有了一个剪枝。再人类智慧的，我们可以钦定最后一个儿子是重儿子，这样剪枝最优。事实上，这已不仅仅是剪枝，而已经达到了 \(O(nlogn)\) 的复杂度了。

考虑证明：计算每个点会被统计几次，如果他在重链上，那么他的信息会被继承上去，不会重复统计，所以说一个点的统计次数就等于这个点到根的重链数量，也就是 \(O(logn)\)，所以总时间复杂度 \(O(nlogn)\)。

虚树

虚树适用于某些题目，这些题目通常需要你做很多次树形DP，只有少部分点是我们DP需要的，我们可以根据他们的祖孙关系建出虚树，这样复杂度就降下来了。