前言

树论是图论的一个比较重要的分支，本文主要总结了一些有关于树的知识点与列题，涉及范围为 noip 以内

树的定义&形态

树有以下常用定义：

1. 有 $n$ 个点，$n - 1$ 条边的有向或无向图
2. 无环的连通无向图

可以分为多颗树的图叫森林

树有一个重要的性质：一颗无向树添加任意一条边后将形成一个环，这样的图叫做基环树

有两种特殊的树：链和菊花图

• 链: $i$ 连 $i + 1$
• 菊花图: $1$ 连 $i$ ($i \neq 1$)

树的基本性质

树的直径

树的直径就是树上任意两点间距离的最大值

求直径一般有两种方式：

1. 两遍 dfs （只能用于正权边）
2. 树形 dp

其时间复杂度都是 $O(n)$

dfs 求直径

首先从任意一点出发，求其余所有点到该点的距离，求出与其距离最大的点 $p$

随后从 $p$ 出发，重复上述过程，直径 $D$ 则为到点 $p$ 的最远点距离

code：

const int N = 1e5 + 5;

int n , p , D;
int dis[N] , fa[N];
vector<int> g[N];

void dfs1(int x , int f){
	for(auto u : g[x]){
		if(u.to == f) continue;
		dis[u.to] = u.w + dis[x];
		if(dis[u.to] > dis[p1]) p1 = u.to;
		fa[u.to] = x;
		
		dfs1(u.to , x);
	}
}

int main(){
	cin >> n;
	
	for(int i = 1 ; i < n ; i ++){
		int x , y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs1(1 , 0);
	dis[p] = 0;
	dfs1(p , 0);
	D = dis[p];
}

dp 求直径

设 $dp_u$ 为在以 $u$ 的子树中从 $u$ 出发的最长路径，显然有如下转移过程($v$ 是 $u$ 子节点)：

$$dp_u = \max(dp_u , dp_v + w(u , v))$$

对于每一个 $u$ 统计答案为：枚举其子节点 $v$，$u$ 在 $v$ 之前的最长路径 $dp_u$ ，加上节点 $v$ 出发的最长路径 $dp_v$ 再加权值即可

$$D = \max(D , dp_u + dp_v + w(u , v))$$

直径的中点

对于直径，有如下推论：若树上所有边边权均为正，则树的所有直径中点重合 （证明详见 OI Wiki）

有了这个推论，我们便可以用 dfs 找到树的中点（边权为 $1$ 时），具体地，在 dfs 上标记每个节点的父亲，设直径端点为 $s , t$，用指针指向 $t$，跳 $\lfloor \frac {D + 1}{2} \rfloor$ 步即可

code

s = p;
for(int i = 1 ; i <= (D + 1) / 2 ; i ++) s = fa[s];

树的重心

树的重心定义为：在树中的某个点 $p$ , $p$ 的所有子树中节点数最大的子树的节点数最小

也就是说：删去点 $p$ 后，所形成的树中节点数最大的树的节点数最小。$p$ 是树上最为平衡的点

重心一般用 dfs 求，对于节点 $p$ ，首先求以 $p$ 为根的子树的节点数，此时按照重心的定义找最小节点 $s$ 即可，即：

$$\min(\max_{u \in s_{son}}(si[u] , n - si[s]))$$

code:

void dfs1(int x , int f){
	int cnt = 0;
	si[x] = 1;
	
	for(auto u : g[x]){
		if(u == f) continue;
		dfs1(u , x);
		si[x] += si[u];
		
		cnt = max(cnt , si[u]);
	}
	cnt = max(cnt , n - si[x]);
	if(cnt < res || (cnt == res && p > x)){
		res = cnt;
		p = x;
	}
}

重心性质

重心有一个重要的性质：树中所有点到某个点的距离和中，到重心的距离和是最小的

树的重心最多有两个，若用两个，则两重心相邻

重心的子树节点数 $\leqslant \frac n2$

LCA

lca 是最近公共祖先的缩写，是树的一个十分重要的知识点

求 lca

求 lca 主要有两种方式：

1. 倍增法 $O((n + q)\log n)$
2. tarjan (离线算法) $O(n + q)$

这里只介绍倍增法求 lca

先回顾暴力求 lca 的过程：对于每一个询问 $(x,y)$，在这里我们令 $dis_x > dis_y$，可以先让 $x$ 一直向上跳，跳到 $dis_x = dis_y$ 的位置随后判断 $x$ 是否是 $y$。若是，则 $y$ 就是 $(x,y)$ 的 lca。若不是，则可以让 $x,y$ 同时向上跳，其第一次相等的节点就是 $(x,y)$ 的 lca

倍增的基本思想就是优化暴力跳的过程（废话），也就是在暴力跳的过程中我们可以根据二进制的思想，一次向上跳 $2^k$ 次，若相同则不跳，不同则跳，这样便可以在 $O(\log n)$ 时间完成查询过程

首先，倍增的关键是预处理 $fa_{x,k}$ 数组，表示 $x$ 的 $2^k$ 级祖先，显然的，$fa_{x,0}$ 就是 $x$ 的父亲可以直接求，处理 $fa_{x,k}$ 的过程在 dfs 中完成，其转移如下

$$fa_{x,k} = fa_{{fa_{x,k-1}},k-1}$$

这个式子基于一个简单的原理 $2^k = 2^{k-1} + 2^{k - 1}$. 同时在 dfs 过程中可以随便处理 $dis$ 数组

随后即可以求 lca 了，对于询问 $(x,y)$，先令 $dis_x > dis_y$，随后将 $x,y$ 跳到同一层，不断令 $x = fa_{x,\log{dis_x-dis_y} -1}$，随后按 $k$ 从大到小的顺序，按上文中的过程跳即可

code

void dfs(int x , int f){
	fa[x][0] = f , d[x] = d[f] + 1;
	for(int i = 1 ; i <= lg[d[x]] ; i ++){
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
	}
	for(int i = 0 ; i < g[x].size() ; i ++){
		int t = g[x][i];
		if(t != f) dfs(t , x);
	}
}

int lca(int x , int y){
	if(d[x] < d[y]) swap(x , y);
	
	while(d[x] > d[y]){
		x = fa[x][lg[d[x] - d[y]] - 1];
	}
	if(x == y) return x;
	for(int i = lg[d[x]] - 1 ; i >= 0 ; i --){
		if(fa[x][i] != fa[y][i]) x = fa[x][i] , y = fa[y][i];
	}
	return fa[x][0];
}

lca 的应用

树上两点距离

树上两点 $(x,y)$ 的距离为：

$$d(x,y) = dis_x + dis_y - 2 \times dis_{lca(x,y)}$$

时间复杂度：$O(\log n)$

树上差分

树上差分是指从 $x$ 到 $y$ 的路径上的节点加 $k$，可以用 $lca$ 快速求解

可以将 $x$ 到 $y$ 的路径分解为两条链，即从 $x$ 到 $lca(x,y)$ 的链和从 $y$ 到 $lca(x,y)$ 的链,将这两条链差分即可，具体地：

设差分数组为 $b$，将 $b_x + k$，$b_y + k$，$b_{lca(x,y)} - k$，$b_{fa_{lca(x,y)}} - k$。注意这里如果将 $b_{lca(x,y)} - 2k$ 的话 $lca(x,y)$ 就加不了了，所以要将 $lca(x,y)$ 的父亲减去 $k$

最后加的话在树上求前缀和，树上前缀和即对每个节点求其子树的和即可

时间复杂度：$O(\log n)$