树论

树上序列

DFS序

从节点1开始的dfs序为：1 2 4 7 8 9 5 3 6

DFS序可以结合树上差分和树状数组可以解决以下问题

1. 单点加：单点修改

2. 子树加：区间修改

3. 路径加：做差分，转换为单点修改

4. 单点求：单点查询，或者做差分后是区间求和

5. 子树求：区间求和

6. 路径求：将点权全部转化为到从根节点到这个点的点权和

欧拉序

欧拉序一

从节点1开始的欧拉序一为：1 2 4 7 7 8 8 9 9 4 5 5 2 3 6 6 3 1

如果进一个点是+x，出一个点是-x，则使用前缀和就可以去求出一个点到根节点的距离

欧拉序二

从节点1开始的欧拉序二为：1 2 4 7 4 8 4 9 4 2 5 2 1 3 6 3 1

将欧拉序上的点相应的深度也求出来作为一个新序列，使用st表维护这个序列，就可以求出两点的lca

树上差分

点差分

点差分解决点权问题

对s-t路径上的点的点权都+1，可以$w[s]+1$，$w[t]+1$，$w[lca]-1$，$w[fa[lca]]-1$。在dfs时有如下代码将点权还原

cpp
1
2
3
4
5
6
7
8
9
int w[400005],ans;
void sum(int x,int fa){
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==fa) continue;
		sum(to,x);
		w[x]+=w[to];
	}
} 

即可将x为根的子树的节点全部使用前缀和得到实际点权

如果结合dfs序和树状数组，则可以获得更大的效率

边差分

边差分和点差分类似。可以将边权转化为较深一点的点权。

如果要在s-t的路径上的边的边权都+1，则需要$w[s]+1$，$w[t]+1$，$w[lca]-2$

LCA

倍增求lca

首先获取log，注意和st表不同，倍增求lca的lg是需要从1开始求的

cpp
1
2
3
int n;
int lg[500001];
for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;

dfs，获取节点信息

cpp
1
2
3
4
5
6
7
8
9
10
11
12
int fa[500001][22];
int dep[500001];
void dfs(int now,int f){
	fa[now][0]=f;
	dep[now]=dep[f]+1;
	for(int i=1;i<=lg[dep[now]];i++){
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	for(int i=head[now];i;i=edge[i].next){
		if(edge[i].to!=f) dfs(edge[i].to,now);
	}
}

然后就可以根据节点信息获得lca

cpp
1
2
3
4
5
6
7
8
9
inline int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y]) x=fa[x][lg[dep[x]-dep[y]]-1];//注意这里减1
	if(x==y) return x;
	for(int k=lg[dep[x]]-1;k>=0;k--){//这里也是要减1 
		if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k];
	} 
	return fa[x][0];
}

st表求lca

st表求lca，只能在树没有修改的情况下。在预处理后，可以做到$O(1)$的查询

首先dfs，获取欧拉序和深度信息

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int dep[500005];
int fir[500005];//点在欧拉序中第一次出现的位置
int ver[1000005];//欧拉序
int r[1000005];//欧拉序位置->点的深度

int tot;
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	fir[x]=++tot;
	ver[tot]=x;
	r[tot]=dep[x];
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==fa) continue;
		dfs(to,x);
		ver[++tot]=x;
		r[tot]=dep[x];
	}
} 

取log（略，参考st表）

st表维护，f为st表维护最小值，rec为取最小值的点

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int rec[1000006][20];
int f[1000006][20];
for(int i=1;i<=tot;i++){
	f[i][0]=r[i];
	rec[i][0]=ver[i];
}
for(int i=1;i<=lg[tot];i++){
	for(int j=1;j<=tot-(1<<i)+1;j++){
		if(f[j][i-1]<f[j+(1<<(i-1))][i-1]){
			f[j][i]=f[j][i-1];
			rec[j][i]=rec[j][i-1];
		}else{
			f[j][i]=f[j+(1<<(i-1))][i-1];
			rec[j][i]=rec[j+(1<<(i-1))][i-1];
		}
	}
}

求lca

cpp
1
2
3
4
5
6
7
8
9
//求lca(a,b)
a=fir[a],b=fir[b];
if(a>b) swap(a,b);
int k=lg[b-a+1];
if(f[a][k]<f[b-(1<<k)+1][k]){
	cout<<rec[a][k]<<endl;
}else{
	cout<<rec[b-(1<<k)+1][k]<<endl;
}

树链剖分求lca

两次dfs，树链剖分，不需要求tree值和value值

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct Point{
	int dep,fa,size,heavy,top,tree,value;
} p[500005];

void dfs1(int x,int fa){
	int mx=-1;
	p[x].size=1;
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==fa) continue;
		p[to].dep=p[x].dep+1;
		p[to].fa=x;
		dfs1(to,x);
		p[x].size+=p[to].size;
		if(p[to].size>mx){
			mx=p[to].size;
			p[x].heavy=to;
		}
	}
}

void dfs2(int x,int fa,int k){
	if(x==0) return;
	p[x].top=k;
	dfs2(p[x].heavy,x,k);
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==fa||to==p[x].heavy) continue;
		dfs2(to,x,to); 
	}
}

求lca

cpp
1
2
3
4
5
6
7
8
9
10
int lca(int x,int y){
	while(p[x].top!=p[y].top){
		if(p[p[x].top].dep>p[p[y].top].dep){
			x=p[p[x].top].fa;
		}else{
			y=p[p[y].top].fa;
		}
	}
	return p[x].dep<p[y].dep? x:y;
}

树的重心

满足下面性质的点叫树的重心

性质

（1）树上每个点为根，都会有若干子树，其中最大子树的大小为这个点的weight。重心的weight最小（重心的定义）

（2）以重心为根，最大子树大小不超过 $\left \lfloor \frac{n}{2} \right \rfloor$ （我们利用这个性质求重心）

（3）树上每个点为根，然后这个树种所有节点到根节点的距离之和（树的重心要求树的每条边的距离都为1）叫做和距离。以重心为根的树的和距离是最小的，如果有两个重心，那么这两个重心的和距离相等

（4）两个树通过一条边连接为一个树，那么新树的重心在原来两个树的重心的连线路径上

（5）在树上添加或删除一个点，重心最多只移动一条边的距离

（6）如果有两个重心，那么以这两个重心为为根的子树大小是相等的。可以逆用（使一个树的重心由两个变为一个）

求法

利用性质1和性质2，一个dfs即可求出。注意重心最多会有两个

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int n;
int size[20004],w[20004];
int g[2];
void dfs(int x,int fa){
	size[x]=1;
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==fa) continue;
		dfs(to,x);
		size[x]+=size[to];
		w[x]=max(w[x],size[to]);
	}
	w[x]=max(w[x],n-size[x]);
	if(w[x]<=n/2){
		g[g[0]!=0]=x;
	}
}

树的直径

树上dp法

设状态 $dis1[x]$ 表示从x这个点往子树走能走的最大距离；$dis2[x]$ 表示从x这个点往子树走能走的次大距离。转移时，对于x的子节点to，两者距离为w，有：

用 $dis1[to]+w$ 尝试更新 $dis1[x]$ 和 $dis2[x]$

如果 $dis1[to]+w>dis1[x]$ 则 $dis1[x]=dis1[to]+w$

反之，如果 $dis1[to]+w>dis2[x]$ 则 $dis2[x]=dis1[to]+w$

最后，直径即为所有的点中 $dis1[x]+dis2[x]$ 最大的值

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int dis1[2000006];
int dis2[2000006];
int ans=0;
void dfs(int x,int fa){
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		int w=edge[i].w;
		if(to==fa) continue;
		dfs(to,x);
		if(dis1[to]+w>dis1[x]){
			dis2[x]=dis1[x];
			dis1[x]=dis1[to]+w;
		}else if(dis1[to]+w>dis2[x]){
			dis2[x]=dis1[to]+w;
		}
	}
	ans=max(ans,dis1[x]+dis2[x]);
}

dfs法

两次dfs。第一次以任意点开始dfs，找到这个距离这个点最短的点x。第二次从点x进行dfs，再找到距离点x最远的点y。xy之间的距离即为直径。相较于树形dp法求直径，dfs法除了求出直径有多长，还能得到直径的端点。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int p,ans,dis[1000006];
void dfs(int x,int fa){
	if(ans<dis[x]){
		ans=dis[x];
		p=x;
	}
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		int w=edge[i].w;
		if(to==fa) continue;
		dis[to]=dis[x]+w;
		dfs(to,x);
	}
}

void find(int x){
	ans=0;
	dis[x]=0;
	dfs(x,0);
}

树的中心

树的中心貌似没有相关题目可以进行评测。仅说一下大致做法

树的中心：树的中心到树中其他节点的最远距离最小

从一个点出发的最长路径有两种情况：从这个点往父节点方向走；从这个点往子树方向走

首先进行一次树形dp，求出每个点往子树方向到达的最长路径 $dis1[]$ 和次长路径 $dis2[]$ 。具体做法和求树的直径部分相同。不同之处在于需要记录 $c1[]$ 和 $c2[]$ 表示 $dis1[]$ 和 $dis2[]$ 是哪个子树转移过来的

再次进行树形dp，求出一个点往父节点方向的最长路径 $u[]$ 。对于一个节点x，其父节点为fa，如果 $c1[fa]!=x$ ，则有 $u[x]=max(dis1[fa],u[fa])+w$。反之，则有 $u[x]=max(dis2[fa],u[fa])+w$

最后，收集答案，即 $ans=min(ans,max(u[x],dis1[x]))$

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
#define _ 2000006
#define int long long
using namespace std;

struct Edge{int next,to,w;} edge[_<<1];
int head[_],size;
inline void add(int u,int v,int w){edge[++size].next=head[u],edge[size].to=v,edge[size].w=w,head[u]=size;}

int dis1[_],dis2[_],c1[_],c2[_];
void dfs1(int x,int fa){
    for(int i=head[x];i;i=edge[i].next){
        int to=edge[i].to;
        int w=edge[i].w;
        if(to==fa) continue;
        dfs1(to,x);
        if(dis1[to]+w>dis1[x]){
            dis2[x]=dis1[x],c2[x]=c1[x];
            dis1[x]=dis1[to]+w,c1[x]=to;
        }else if(dis1[to]+w>dis2[x]) dis2[x]=dis1[to]+w,c2[x]=to;
    }
}

int u[_];
void dfs2(int x,int fa){
    for(int i=head[x];i;i=edge[i].next){
        int to=edge[i].to;
        int w=edge[i].w;
        if(to==fa) continue;
        if(c1[x]!=to) u[to]=max(dis1[x],u[x])+w;
        else u[to]=max(dis2[x],u[x])+w;
        dfs2(to,x);
    }
}

signed main(){
    ios::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=1,uu,vv,ww;i<n;i++) cin>>uu>>vv>>ww,add(uu,vv,ww),add(vv,uu,ww);
    dfs1(1,0);dfs2(1,0);
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++) ans=min(ans,max(u[i],dis1[i]));
    cout<<ans;
    return 0;
} 

生成树

最小生成树

prim算法能做的kruskal似乎都能做。就不写prim算法了

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int mst=0;
void kruskal(){
	int cnt=0;
	for(int i=1;i<=m;i++){
		int u=find(e[i].from);
		int v=find(e[i].to);
		if(u==v) continue;
        //注意不是add(u,v,...);
		add(e[i].from,e[i].to,e[i].w);
		add(e[i].to,e[i].from,e[i].w);
		e[i].flag=true;
		mst+=e[i].w;
		fa[u]=v;
		cnt++;
		if(cnt==n-1) break;
	}
}

次小生成树

非严格次小生成树

先求一个最小生成树，然后枚举非树边，将树上非树边两个端点之间路径经过的最大边权减去，加上非树边边权，可得到一个新的生成树。枚举所有非树边，新生成树中最小的一个就是非严格次小生成树

严格次小生成树

与非严格次小生成树不同的是，如果非树边两个端点之间路径经过的最大边权等于这个非树边的边权，那么这个最大边权是不能选择的，我们需要再找一个次大的。在树链剖分线段树上不仅维护区间最大值，还要维护区间严格次大值

求四个数中的严格次大值，没有就返回0

cpp
1
2
3
4
5
6
7
8
9
10
inline int getse(int a,int b,int c,int d){
	int e[5]={a,b,c,d};
	sort(e,e+4,[](int a,int b){
		return a>b;
	});
	for(int i=1;i<3;i++){
		if(e[i]!=e[0]) return e[i];
	}
	return 0;
}

query

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
int query(int x,int y,int d){
	int ans=0;
	while(p[x].top!=p[y].top){
		if(p[p[x].top].dep<p[p[y].top].dep) swap(x,y);
		pii t=query(1,1,n,p[p[x].top].tree,p[x].tree);
		x=p[p[x].top].fa;
		ans=max(ans,(t.first==d)? t.second:t.first);
	}
	if(p[x].dep>p[y].dep) swap(x,y);
	pii t=query(1,1,n,p[x].tree+1,p[y].tree);	
	ans=max(ans,(t.first==d)? t.second:t.first);
	return ans;
}

查询的时候，注意query得到的边权不能为0，且求出的次小生成树要大于最小生成树

cpp
1
2
3
4
5
6
    int ans=0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=m;i++){
		if(e[i].flag) continue;
		int tmp=mst-query(e[i].from,e[i].to,e[i].w)+e[i].w;
		if(tmp<ans&&tmp!=mst+e[i].w&&tmp>mst) ans=tmp;
	}

瓶颈生成树

树上最大边权最小的树。根据kruskal求解最小生成树的过程可知，最小生成树一定是瓶颈生成树。瓶颈生成树不一定是最小生成树

Kruskal重构树

性质

（1）若最小生成树有n个节点，那么重构树有且仅有 $2n-1$ 个节点。（用于判断数组开多大）

（2）重构树上两个叶子节点x和y之间路径上的点（不包括x和y）和最小生成树上x到y的路径上的边一一对应

（3）在重构树中，节点的权值随深度增大而增大或减小（具有单调性，可以结合树上倍增）

（4）由性质3和4可知，重构树上x和y的lca的权值等于原图x到y的瓶颈大小

（5）由单调性可知，满足与一个点的瓶颈大小小于某个值的所有的点都在重构树中的同一子树中

求重构树

首先将边排序。将边按递增或递减排序，得到的重构树分别满足大根堆和小根堆的性质

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int cnt,p;//p为重构树中的节点数量
void kruskal(){
	sort(e+1,e+m+1,[](Edge a,Edge b){
		return a.w<b.w;
	});
	for(int i=1;i<=n*2;i++) fa[i]=i;
	cnt=0,p=n;
	for(int i=1;i<=m;i++){
		int u=find(e[i].from);
		int v=find(e[i].to);
		if(u==v) continue;
		add(++p,u);//直接建单向边
		add(p,v);
        //注意，和求最小生成树不同，不是add(..,e[i].to/from)  
		w[p]=e[i].w;
		fa[u]=p;
		fa[v]=p;
		cnt++;
		if(cnt==n-1) break;
	}
}

然后就得到了一个以p为根的kruskal重构树

树链剖分

点信息的结构体

cpp
1
2
3
struct Info{
	int dep,size,heavy,fa,value,top,tree;
} p[30001];

第一次dfs，求出dep,size,heavy,fa

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs1(int x,int fa){
	int mx=-1;
	p[x].size=1;
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==fa) continue;
		p[to].dep=p[x].dep+1;
		p[to].fa=x;
		dfs1(to,x);
		p[x].size+=p[to].size;
		if(p[to].size>mx){
			p[x].heavy=to;
			mx=p[to].size;
		}
	}
}

第二次dfs，将dfs序和线段树联系起来

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int total;
int num[30001];
void dfs2(int x,int fa,int k){
	if(x==0) return;
	p[x].top=k;
	p[x].tree=++total;
	num[total]=x;
	dfs2(p[x].heavy,x,k);
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==fa) continue;
		if(to==p[x].heavy) continue;
		dfs2(to,x,to);
	}
}

num表示线段树相应位置的节点编号是多少

然后根据 $num[]$ 建立线段树

维护点权

以计算路径上点权之和为例

cpp
1
2
3
4
5
6
7
8
9
10
11
int query(int x,int y){
	int ans=0;
	while(p[x].top!=p[y].top){
		if(p[p[x].top].dep<p[p[y].top].dep) swap(x,y);
		ans+=query(1,1,n,p[p[x].top].tree,p[x].tree);
		x=p[p[x].top].fa;
	}
	if(p[x].dep>p[y].dep) swap(x,y);
	ans+=query(1,1,n,p[x].tree,p[y].tree);
	return ans;
}

维护边权

需要点权转边权

由于一个点只有一个父节点，所以把边 $(fa,son,w)$ 的边视为节点 $son$ 的点权

其余和维护点权类似。最后在一条链上跳时，注意左端点+1

cpp
1
2
3
4
5
...
    if(p[x].dep>p[y].dep) swap(x,y);
	ans+=query(1,1,n,p[x].tree+1,p[y].tree);
	return ans;
...

还需要注意，+1后可能x>y，因此在线段树查询的时候需要特判

cpp
1
2
3
int query(int k,int l,int r,int x,int y){
	if(x>y) return 0;
...