专栏文章

学习笔记-图论

YYGBC_
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzu0vu
此快照首次捕获于
2025/12/01 18:15
3 个月前
此快照最后确认于
2025/12/01 18:15
3 个月前
查看原文

图论

关于图的一些基本定义见 图论相关概念 - OI Wiki (oi-wiki.org)。

0. 图的存储

之所以写在最前面，是因为它是所有图操作的基础。

邻接矩阵

用矩阵形式存储点对 u,vu,v 的可达性或是边权，优点是方便，可以 O(1)O(1) 查询点对的关系。缺点空间复杂度劣，遍历图较慢。

邻接表

利用可以动态分配内存的数据结构（如 std::vector），可以做到接近 O(1)O(1) 插入，O(n+m)O(n+m) 的空间复杂度和遍历，是比较常用的存图结构。

边集数组

直接将边的点对，边权等存入一个数组，优点是即为简洁，插入快，空间复杂度好，缺点是遍历图较劣。适用于要遍历所有边的场景。

链式前向星

用类似链表的结构存储每个节点出发的边，与邻接表类似。（似乎可以用 std::list 实现？）
下面是所有存图方式的核心代码：
CPP
constexpr int X=1e3+5,Y=1e5+5;
int N,M;

int G1[X][X];                // 邻接矩阵 

struct Edge2{
	int v,w;
	Edge2(): v(0), w(0) {}
	Edge2(int a,int b): v(a), w(b) {}
	bool operator< (const Edge2 &a) const { return w<a.w; }
	bool operator> (const Edge2 &a) const { return w>a.w; }
}; 
vector<Edge2> G2[X];         // 邻接表 

struct Edge3{
	int u,v,w;
	Edge3(): u(0), v(0), w(0) {}
	Edge3(int a,int b,int c): u(a), v(b), w(c) {}
	bool operator< (const Edge3 &a) const { return w<a.w; }
	bool operator> (const Edge3 &a) const { return w>a.w; }
}; 
Edge3 E[Y];                  // 边集数组 

struct Edge4{
	int to,w,next;
}edge[Y]; 

int head[X],cnt;

void init()
{
	for(int i=1;i<=N;i++) head[i]=-1;
	cnt=0;
}
void add_edge(int u,int v,int w)
{
	edge[cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}                            // 链式前向星

1. 图的遍历

与搜索相同，图的遍历也有 BFS（广度优先搜索），DFS（深度优先搜索）。

1.1 BFS

由队列实现的算法。首先将起点放入队列，每次将遍历的节点放入队列，直到队列清空。

1.2 DFS

递归实现。每次遍历到一个节点，就递归到下一层进行遍历。
给出两种遍历的算法。
CPP
constexpr int X=1e4+5;

int N,M;
bool vis[X];
vector<int> G[X];

void DFS(int u)
{
	vis[u]=1;
	for(int v:G[u]) 
		if(!vis[v]) DFS(v);
}
void BFS(int s)
{
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int u=q.front(); 
		vis[u]=1; q.pop();
		for(int v:G[u])
			if(!vis[v]) q.push(v);
	}
}

2. 拓扑排序

若对一个 DAG 上的节点进行定序，保证所有节点的出点在这个节点之后，则这个序列称作这个图的拓扑序。
求拓扑序有两种方式：BFS （Kahn\text{Kahn} 算法）和 DFS。时间复杂度为 O(n+m)O(n+m)。
BFS （Kahn\text{Kahn} 算法）实现：
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=105;

int N,in[X];
vector<int> G[X],res;

void Kahn()
{
	queue<int> q;
	for(int i=1;i<=N;i++)
		if(!in[i]) q.push(i);
	while(q.size()){
		int u=q.front(); q.pop();
		res.push_back(u);
		for(int v:G[u]){
			in[v]--;
			if(!in[v]) q.push(v);
		}
	}
}

int main() 
{
	cin>>N;
	for(int i=1,a;i<=N;i++){
		cin>>a;
		while(a){
			G[i].push_back(a);
			in[a]++; cin>>a;
		}
	}
	Kahn();
	for(int i:res) cout<<i<<' ';
}
DFS 实现：
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=105;

int N;
bool vis[X];
vector<int> G[X];
stack<int> st; 

void DFS(int u)
{
	vis[u]=1;
	for(int v:G[u])
		if(!vis[v]) DFS(v);
	st.push(u);
}

int main() 
{
	cin>>N;
	for(int i=1,a;i<=N;i++){
		cin>>a;
		while(a){
			G[i].push_back(a);
			cin>>a;
		}
	}
	for(int i=1;i<=N;i++)
		if(!vis[i]) DFS(i);
	while(!st.empty()){
		cout<<st.top()<<' ';
		st.pop();
	}
}

3.最短路

应该是图论知识框架中最常使用的一个知识点。

3.1 单源最短路径

Dijkstra\text{Dijkstra}

使用最广泛的最短路算法，适用于求非负边权图的单源最短路径。
每次选择未更新的离起点最近的节点，以它为中转点更新其他节点的最短路径，直到所有节点被更新。
共更新 nn 轮，每轮更新节点 O(n)O(n)，总共松弛 O(m)O(m) 次路径，所以朴素实现的时间复杂度为 O(n2+m)=O(n2)O(n^2+m)=O(n^2)。
下面是朴素实现的代码：
CPP
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
constexpr int X=1e5+5;

int N,M,s,dis[X];
bool vis[X];

struct Edge{
	int v,w;
	Edge(): v(0), w(0) {}
	Edge(int a,int b): v(a), w(b) {}
};
vector<Edge> G[X];

void Dijkstra(int s)
{
	for(int i=1;i<=N;i++) dis[i]=INF;
	dis[s]=0;
	for(int i=1;i<=N;i++){
		int u=0,mind=INF<<1;
		for(int j=1;j<=N;j++){
			if(vis[j]) continue;
			if(dis[j]<mind) u=j, mind=dis[j];
		}
		vis[u]=1;
		for(Edge e:G[u])
			if(dis[u]+e.w<dis[e.v])
				dis[e.v]=dis[u]+e.w;
	}
}

int main()
{
	cin>>N>>M>>s;
	for(int i=1,u,v,w;i<=M;i++){
		cin>>u>>v>>w;
		G[u].emplace_back(v,w);
	}
	Dijkstra(s);
	for(int i=1;i<=N;i++) cout<<dis[i]<<' ';
	return 0;
}
有一个经典的优化，是将路径长度用堆存储，就省去了每次 O(n)O(n) 查找最小值。
最坏会弹出 O(n)O(n) 次节点，做 O(m)O(m) 松弛操作，优先队列实现的复杂度为 O((m+n)log⁡m)=O(mlog⁡m)O((m+n)\log m)=O(m\log m)，若使用能够 O(1)O(1) Decrease_key 操作的二叉堆或是线段树，复杂度为 O(mlog⁡n)O(m\log n)，斐波那契堆能将复杂度进一步优化为 O(nlog⁡n+m)O(n\log n+m)，但这些做法实际并不一定跑得更快。
下面给出优先队列实现的 Dijkstra\text{Dijkstra}。
CPP
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
constexpr int X=1e5+5;

int N,M,s,dis[X];
bool vis[X];

struct Edge{
	int v,w;
	Edge(): v(0), w(0) {}
	Edge(int a,int b): v(a), w(b) {}
};
vector<Edge> G[X];

struct Node{
	int u,d;
	Node(): u(0), d(0) {}
	Node(int a,int b): u(a), d(b) {}
	bool operator< (const Node &a) const { return d<a.d; }
	bool operator> (const Node &a) const { return d>a.d; }
};
priority_queue<Node,vector<Node>,greater<Node>> q;

void Dijkstra(int s)
{
	for(int i=1;i<=N;i++) dis[i]=INF;
	q.emplace(s,0); dis[s]=0;
	while(!q.empty()){
		Node n=q.top(); q.pop();
		if(vis[n.u]) continue;
		vis[n.u]=1;
		for(Edge e:G[n.u]){
			if(vis[e.v]) continue;
			if(n.d+e.w<dis[e.v]){
				dis[e.v]=n.d+e.w;
				q.emplace(e.v,dis[e.v]);
			}
		}
	}
}

int main()
{
	cin>>N>>M>>s;
	for(int i=1,u,v,w;i<=M;i++){
		cin>>u>>v>>w;
		G[u].emplace_back(v,w);
	}
	Dijkstra(s);
	for(int i=1;i<=N;i++) cout<<dis[i]<<' ';
	return 0;
}

Bellman-Ford\text{Bellman-Ford}

Dijkstra\text{Dijkstra} 唯一的缺点是不能跑负权图，因为其每次贪心的思路不能保证先被确定的节点路径长度是最短路径。
Bellman-Ford\text{Bellman-Ford} 是一种可以跑负权图的单源最短路径算法，其核心是按边松弛每一个节点，共 nn 轮。这样每一个节点都能保证被所有路径及边松弛。
时间复杂度显然是 O(nm)O(nm)。
Bellman-Ford\text{Bellman-Ford} 通常使用由队列优化的 SPFA\text{SPFA} 实现，所以在此不放代码。

SPFA\text{SPFA}

由队列优化的 Bellman-Ford\text{Bellman-Ford}，其实现方式是将每一轮被松驰过的节点去松弛其他节点。其在随机图中的表现十分优秀，与 Dijkstra\text{Dijkstra} 相当，但其最坏复杂度仍是 O(nm)O(nm)。
下面给出 SPFA\text{SPFA} 的代码实现。
CPP
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
constexpr int X=1e5+5;

int N,M,s,dis[X],pre[X];
bool inq[X];

struct Edge{
	int v,w;
	Edge(): v(0), w(0) {}
	Edge(int a,int b): v(a), w(b) {}
};
vector<Edge> G[X];

queue<int> q; 

bool SPFA(int s)
{
	for(int i=1;i<=N;i++) dis[i]=INF;
	q.push(s); dis[s]=0, inq[s]=1;
	while(!q.empty()){
		int u=q.front(); 
		q.pop(); inq[u]=0;
		for(Edge e:G[u]){
			if(dis[u]+e.w<dis[e.v]){
				dis[e.v]=dis[u]+e.w;
				pre[e.v]=pre[u]+1;
				if(pre[e.v]>=N) return 1;
				if(!inq[e.v]){
					q.push(e.v); 
					inq[e.v]=1;
				} 
			}
		}
	}
	return 0;
}

int main()
{
	cin>>N>>M>>s;
	for(int i=1,u,v,w;i<=M;i++){
		cin>>u>>v>>w;
		G[u].emplace_back(v,w);
	}
	SPFA(s);
	for(int i=1;i<=N;i++) cout<<dis[i]<<' ';
	return 0;	
}

3.2 全源最短路径

Floyd\text{Floyd}

全名 Floyd-Warshell\text{Floyd-Warshell}，使用较多的全源最短路径算法。
其本质是动态规划算法，设 fk,i,jf_{k,i,j} 为松弛到 kk 点，i→ji\rightarrow j 的最短路径，则有转移式如下：
fk,i,j=min⁡(fk−1,i,j,fk−1,i,k+fk−1,k,j)f_{k,i,j}=\min(f_{k-1,i,j},f_{k-1,i,k}+f_{k-1,k,j})
显然这个转移为 O(1)O(1)，状态数 O(n3)O(n^3)，所以 Floyd\text{Floyd} 的复杂度为 O(n3)O(n^3)。
下面给出 Floyd\text{Floyd} 的实现代码，实际实现中常常在原邻接矩阵中转移。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=505;

int N,M;
int G[X][X]; 

void Floyd()
{
	for(int k=1;k<=N;k++)
		for(int i=1;i<=N;i++)
			for(int j=1;j<=N;j++)
				G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
}

int main()
{
	cin>>N>>M;
	memset(G,0x3f,sizeof G);
	for(int i=1;i<=N;i++) G[i][i]=0;
	for(int i=1,u,v,w;i<=M;i++){
		cin>>u>>v>>w;
		G[u][v]=min(G[u][v],w);
		G[v][u]=min(G[v][u],w);
	}
	Floyd();
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++) cout<<G[i][j]<<' ';
		cout<<'\n';
	}
	return 0;
}

Johnson\text{Johnson}

一种在稠密图比 Floyd\text{Floyd} 更优的全员最短路径算法。其本质是做 nn 次 Dijkstra\text{Dijkstra}，但是可以处理负边权。
算法的核心是建立一个源点 00，并向每一个节点建立一条边权为 00的负权边，从此源点开始做一遍 Bellman-Ford\text{Bellman-Ford}，记 huh_u 为从 00 节点到点 uu 的最短路径。然后将原图的每条边（从 uu 到 vv，边权为 ww）的边权改为 hu−hv+wh_u-h_v+w。然后跑 nn 次 Dijkstra\text{Dijkstra} 即可。
注意最后的的路径 disi,jdis_{i,j} 要修改为 disi,j−hi+hjdis_{i,j}-h_i+h_j。
Bellman-Ford\text{Bellman-Ford} 预处理为 O(nm)O(nm)，做 nn 轮 Dijkstra\text{Dijkstra} 复杂度 O(nmlog⁡m)O(nm\log m)（优先队列实现），所以时间复杂度为 O(nmlog⁡m)O(nm\log m)。下面给出实现代码。
CPP
#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
constexpr int X=3e3+5;

int N,M;
long long res;

struct Edge{
	int v,w;
	Edge(): v(0), w(0) {}
	Edge(int a,int b): v(a), w(b) {}
};
vector<Edge> G[X];

struct Node{
	int u,d;
	Node(): u(0), d(0) {}
	Node(int a,int b): u(a), d(b) {}
	bool operator< (const Node &a) const { return d<a.d; }
	bool operator> (const Node &a) const { return d>a.d; }
};

int h[X],pre[X];
bool inq[X];

bool SPFA()
{
	for(int i=0;i<=N;i++) h[i]=INF;
	queue<int> q;
	q.push(0); inq[0]=1, h[0]=0;
	while(!q.empty()){
		int u=q.front(); 
		q.pop(); inq[u]=0;
		for(Edge e:G[u]){
			if(h[u]+e.w<h[e.v]){
				h[e.v]=h[u]+e.w;
				pre[e.v]=pre[u]+1;
				if(pre[e.v]>N) return 1;
				if(!inq[e.v]){
					q.push(e.v);
					inq[e.v]=1;
				}
			}
		}
	}
	return 0;
} 

int dis[X][X];
bool vis[X];

void Dijkstra(int s)
{
	for(int i=1;i<=N;i++) dis[s][i]=INF, vis[i]=0;
	priority_queue<Node,vector<Node>,greater<Node>> q;
	q.emplace(s,0); dis[s][s]=0;
	while(!q.empty()){
		Node n=q.top(); q.pop();
		if(vis[n.u]) continue;
		vis[n.u]=1;
		for(Edge e:G[n.u]){
			if(vis[e.v]) continue;
			if(n.d+e.w<dis[s][e.v]){
				dis[s][e.v]=n.d+e.w;
				q.emplace(e.v,dis[s][e.v]);
			}
		}
	}
	return ;
}

int main()
{
	cin>>N>>M;
	for(int i=1;i<=N;i++) G[0].emplace_back(i,0);
	for(int i=1,u,v,w;i<=M;i++){
		cin>>u>>v>>w;
		G[u].emplace_back(v,w);
	}
	bool neg=SPFA();
	if(neg){
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=N;i++)
		for(Edge &e:G[i])
			e.w+=h[i]-h[e.v];
	for(int i=1;i<=N;i++){
		Dijkstra(i);
		for(int j=1;j<=N;j++)
			if(dis[i][j]!=INF) dis[i][j]+=h[j]-h[i];
	} 
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++)  res+=j*dis[i][j];
		cout<<res<<'\n'; res=0;
	}
	return 0;
}

3.3 最短路的应用

传递闭包

Floyd\text{Floyd} 的经典应用。求解图中任意点对的可达性。
令 ai,ja_{i,j} 为从 ii 到 jj 是否可达（true\text{true} 或 false\text{false}）使用 Floyd\text{Floyd} 可以写出如下转移：
fk,i,j=fk−1,i,j∨(fk−1,i,k∧ak,j)f_{k,i,j}=f_{k-1,i,j}\lor (f_{k-1,i,k}\land a_{k,j})
我们在原矩阵进行转移，发现到只有 fi,k=truef_{i,k}=\text{true} 时 转移才有意义，所以我们可以把第二位压入 bitset 一并转移。
朴素 Floyd\text{Floyd} 的复杂度为 O(n3)O(n^3)，用 bitset 可以优化至 O(n3ω)O(\frac{n^3}{\omega}) 。
下面给出实现代码。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=1005;

int N;
bitset<X> G[X];

void Floyd()
{
	for(int k=1;k<=N;k++)
		for(int i=1;i<=N;i++)
			if(G[i][k]) G[i]|=G[k];
}

int main()
{
	cin>>N;
	for(int i=1;i<=N;i++)
		for(int j=1,b;j<=N;j++){
			cin>>b;
			if(b) G[i][j]=b;
		}
	Floyd();
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++) cout<<(G[i][j]?1:0)<<' ';
		cout<<'\n';
	}
	return 0;
}

负环

若图中存在负环，则最短路不存在。
判断负环最简单的方式是记录一个节点 uu 的最短路径中前驱结点的数量 preupre_u，若任意节点的 prepre 值大于等于 nn，则图中存在负环。
模板代码，用 SPFA\text{SPFA} 实现。时间复杂度为 O(nm)O(nm)。
CPP
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
constexpr int X=1e5+5;

int T,N,M,dis[X],pre[X];
bool inq[X];

struct Edge{
	int v,w;
	Edge(): v(0), w(0) {}
	Edge(int a,int b): v(a), w(b) {}
};
vector<Edge> G[X];



bool SPFA(int s)
{
	for(int i=1;i<=N;i++) dis[i]=INF;
	queue<int> q; 
	q.push(s); dis[s]=0, inq[s]=1;
	while(!q.empty()){
		int u=q.front(); 
		q.pop(); inq[u]=0;
		for(Edge e:G[u]){
			if(dis[u]+e.w<dis[e.v]){
				dis[e.v]=dis[u]+e.w;
				pre[e.v]=pre[u]+1;
				if(pre[e.v]>=N) return 1;
				if(!inq[e.v]){
					q.push(e.v); 
					inq[e.v]=1;
				} 
			}
		}
	}
	return 0;
}

void solve()
{
	for(int i=1;i<=N;i++){
		inq[i]=pre[i]=0;
		G[i].clear();
	} 
	cin>>N>>M;
	for(int i=1,u,v,w;i<=M;i++){
		cin>>u>>v>>w;
		G[u].emplace_back(v,w);
		if(w>=0) G[v].emplace_back(u,w);
	}
	if(SPFA(1)) cout<<"YES\n";
	else cout<<"NO\n";
	return ;	
}

int main()
{
	cin>>T;
	while(T--) solve();
}

差分约束

求解不等式组（又称差分约束系统）。根据三角形不等式 disj−disi≤w(i,j)dis_j-dis_i\le w(i,j) 可以将变量看作节点建图（若有 xi+xj≤ax_i+x_j\le a 则建一条边权为 aa，
j→ij\rightarrow i 的有向边）。为保证图的联通以及计算不等式组的解，还要建一个超级源点 00，向每一个节点建一条边权为 00 的有向边。不等式无解当且仅当图中出现负环。
下边给出代码，最短路由 SPFA\text{SPFA} 实现，时间复杂度 O(nm)O(nm)。
CPP
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
constexpr int X=5e3+5; 

int N,M,dis[X],pre[X];
bool inq[X];

struct Edge{
	int v,w;
	Edge(): v(0), w(0) {}
	Edge(int a,int b): v(a), w(b) {}
};

vector<Edge> G[X];
queue<int> q;

bool SPFA()
{
	for(int i=0;i<=N;i++) dis[i]=INF;
	q.push(0); dis[0]=0, inq[0]=1;
	while(!q.empty()){
		int u=q.front(); q.pop();
		inq[u]=0;
		for(Edge e:G[u]){
			if(dis[u]+e.w<dis[e.v]){
				dis[e.v]=dis[u]+e.w;
				pre[e.v]=pre[u]+1;
				if(pre[e.v]>N) return 1;
				if(!inq[e.v]){
					q.push(e.v);
					inq[e.v]=1;
				}
			}
		}
	}
	return 0;
}

int main()
{
	cin>>N>>M;
	for(int i=1;i<=N;i++) G[0].emplace_back(i,0);
	for(int i=1,u,v,w;i<=M;i++){
		cin>>v>>u>>w;
		G[u].emplace_back(v,w);
	}
	bool res=SPFA();
	if(res) cout<<"NO";
	else for(int i=1;i<=N;i++) cout<<dis[i]<<' ';
	return 0;
}

4. 最小生成树

若以一无向图图中的边构成一颗无根树，使得在图联通的前提下边权和最小，则此无根树为图的最小生成树。此边权和也是使原图联通的最小边权和。
求解最小生成树有三种算法：适用于稀疏图的 Kruskal\text{Kruskal} 算法，适用于稠密图的 Prim\text{Prim} 算法，以及较冷门的 Boruvka\text{Boruvka} 算法。

Kruskal\text{Kruskal}

一种按边贪心的求最小生成树算法。先将边排序，然后从小到大选边，若边的两端节点已经联通就跳过。最后得到的就是最小生成树。
排序复杂度为 O(mlog⁡m)O(m\log m)，并查集复杂度为 O(mlog⁡n)O(m\log n) 或 O(mα(n))O(m\alpha(n))。总时间复杂度为 O(mlog⁡m)O(m\log m) ，瓶颈在于排序，所以常数极小。
给出代码实现，注意要特判不连通的情况。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int INF=1e9;
constexpr int X=5e3+5;
constexpr int Y=2e5+5;

int N,M,res;

struct Edge{
	int u,v,w;
	bool operator< (const Edge &a) const { return w<a.w; }
}E[Y]; 

int fa[X],siz[X];

inline int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
inline bool merge(int x,int y)
{
	x=find(x), y=find(y);
	if(x==y) return 0;
	if(siz[x]>siz[y]) swap(x,y);
	fa[x]=y, siz[y]+=siz[x];
	return 1;
	
}

int Kruskal()
{
	int res=0,cnt=0;
	for(int i=1;i<=N;i++) fa[i]=i, siz[i]=1;
	for(int i=1;i<=M;i++){
		if(merge(E[i].u,E[i].v)) cnt++, res+=E[i].w;
		if(cnt==N-1) break;
	}
	if(cnt<N-1) return INF;
	return res;
}

int main()
{
	cin>>N>>M;
	for(int i=1,u,v,w;i<=M;i++)
		cin>>E[i].u>>E[i].v>>E[i].w;
	sort(E+1,E+M+1);
	res=Kruskal();
	if(res==INF) cout<<"orz";
	else cout<<res; 
}

Prim\text{Prim}

Prim\text{Prim} 算法是一种单源增广算法，从一个点贪心寻找最短边向外扩张。每一次选择一个与当前连通块距离最近的节点加进连通块，并更新其他节点的距离。
可以发现与 Dijkstra\text{Dijkstra} 算法十分相似，所以朴素复杂度为 O(n2)O(n^2)。同样可以使用堆优化，但不一定比 Kruskal\text{Kruskal} 更快。
下面给出朴素 Prim\text{Prim} 的代码实现。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int INF=1e9;
constexpr int X=5e3+5;
constexpr int Y=2e5+5;

int N,M,res,dis[X];
bool vis[X];

struct Edge{
	int v,w;
	Edge(): v(0), w(0) {}
	Edge(int a,int b): v(a), w(b) {}
};
vector<Edge> G[X];

int Prim()
{
	int res=0,cnt=0;
	for(int i=1;i<=N;i++) dis[i]=INF, vis[i]=0;
	dis[1]=0;
	for(int i=1;i<=N;i++){
		int u=0,mind=INF<<1;
		for(int j=1;j<=N;j++){
			if(vis[j]) continue;
			if(dis[j]<mind) u=j, mind=dis[j];
		}
		vis[u]=1, res+=dis[u], dis[u]=0;
		for(Edge e:G[u])
			if(e.w<dis[e.v]) 
				dis[e.v]=e.w;
	}
	return res;
}

int main()
{
	cin>>N>>M;
	for(int i=1,u,v,w;i<=M;i++){
		cin>>u>>v>>w;
		G[u].emplace_back(v,w);
		G[v].emplace_back(u,w);
	}
	res=Prim();
	if(res>=INF) cout<<"orz";
	else cout<<res; 
}

Boruvka\text{Boruvka}

一个多源增广的最小生成树算法，较为冷门。
初始时将每个点当作一个连通块，并遍历边集数组，寻找每个连通块向外最短的边，并将这些边加入最小生成树中。
由于每次连通块数量至少减半，所以最多更新 O(log⁡n)O(\log n) 次，每次遍历边集数组并使用并查集维护连通块，所以单次迭代复杂度为 O(mα(n))O(m\alpha(n)) 所以总时间复杂度为 O(mα(n)log⁡n)O(m\alpha(n)\log n)。
下面给出代码。注意边权可能相等，所以连通块之间可能构成环，所以要使用第二关键字对同边权的边进行明确比较，可使用边的编号。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int INF=1e9;
constexpr int X=5e3+5;
constexpr int Y=2e5+5;

int N,M,res;

struct Edge{
	int u,v,w,id;
	bool operator< (const Edge &a) const { return (w==a.w)?id<a.id:w<a.w; }
	bool operator> (const Edge &a) const { return (w==a.w)?id>a.id:w>a.w; }
}E[Y];

int fa[X],siz[X];

int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
	x=find(x), y=find(y);
	if(x==y) return ;
	if(siz[x]>siz[y]) swap(x,y);
	fa[x]=y, siz[y]+=siz[x];
}

int e[X];
bool vis[Y];

int Boruvka()
{
	for(int i=1;i<=N;i++) fa[i]=i,siz[i]=1;
	int cnt=0, res=0; 
	bool upd=1;
	while(upd){
		for(int i=1;i<=N;i++) e[i]=0; upd=0;
		for(int i=1;i<=M;i++){
			if(vis[i]) continue;
			int p=find(E[i].u), q=find(E[i].v);
			if(p==q) continue;
			if(E[i]<E[e[p]]) e[p]=i;
			if(E[i]<E[e[q]]) e[q]=i;
		}
		for(int i=1;i<=N;i++){
			if(!e[i]||vis[e[i]]) continue;
			upd=1, vis[e[i]]=1;
			cnt++, res+=E[e[i]].w,
			merge(E[e[i]].u,E[e[i]].v);
		}
	}
	if(cnt!=N-1) return INF;
	return res;
}

int main()
{
	cin>>N>>M;
	E[0]={0,0,INF,INF};
	for(int i=1;i<=M;i++){
		cin>>E[i].u>>E[i].v>>E[i].w;
		E[i].id=i;
	}
	res=Boruvka();
	if(res==INF) cout<<"orz";
	else cout<<res;
	return 0;
}

5. 连通性相关（Tarjan\text{Tarjan}）

这一块主要是求无向图的割点，割边，双连通分量，以及有向图的强连通分量。都可以用 Tarjan\text{Tarjan} 算法实现，时间复杂度 O(n+m)O(n+m)。

5.1 无向图的连通性

割点

在无向图中，若一个点被删去，图中的连通分量数增加了，则这个点为割点。
下面给出 Tarjan\text{Tarjan} 算法求割点的代码。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=2e4+5;

int N,M,R,res;
int dfn[X],low[X],idx;
bool iscut[X];
vector<int> G[X];

void Tarjan(int u)
{
	dfn[u]=low[u]=++idx;
	int son=0;
	for(int v:G[u]){
		if(!dfn[v]){
			Tarjan(v); son++;
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&u!=R) 
				iscut[u]=1;
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(son>=2&&u==R) iscut[u]=1;
}

int main()
{
	cin>>N>>M;
	for(int i=1,u,v;i<=M;i++){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1;i<=N;i++)
		if(!dfn[i]) R=i, Tarjan(i);
	for(int i=1;i<=N;i++)
		if(iscut[i]) res++;
	cout<<res<<'\n';
	for(int i=1;i<=N;i++)
		if(iscut[i]) cout<<i<<' ';
	return 0;
}

点双连通分量

定义见 双连通分量 - OI Wiki (oi-wiki.org)。
给出模板代码。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=5e5+5;

int N,M,R,dfn[X],low[X],idx;
int st[X],top,cnt;
vector<int> G[X];
vector<int> bcc[X];

void Tarjan(int u)
{
	dfn[u]=low[u]=++idx;
	st[++top]=u;
	if(u==R&&G[u].empty()){
		bcc[++cnt].push_back(u);
		return ;
	} 
	int son=0;
	for(int v:G[u]){
		if(!dfn[v]){
			son++;
			Tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				cnt++;
				do bcc[cnt].push_back(st[top]);
				while(st[top--]!=v);
				bcc[cnt].push_back(u);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

int main()
{
	cin>>N>>M;
	for(int i=1,u,v;i<=M;i++){
		cin>>u>>v;
		if(u==v) continue;
		G[u].push_back(v);
		G[v].push_back(u); 
	}
	for(int i=1;i<=N;i++)
		if(!dfn[i]) R=i, Tarjan(i);
	cout<<cnt<<'\n';
	for(int i=1;i<=cnt;i++){
		cout<<bcc[i].size()<<' ';
		for(int j:bcc[i]) cout<<j<<' ';
		cout<<'\n';
	}
	return 0;
}

割边

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。
给出代码。
CPP
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
constexpr int X=5e5+5,Y=2e6+5;

int N,M,cnt,dfn[X],low[X],idx;
bool isbridge[Y];
vector<pii> G[X];

void Tarjan(int f,int u)
{
	bool flag=0;
	dfn[u]=low[u]=++idx;
	for(pii p:G[u]){
		int v=p.fi, id=p.se;
		if(!dfn[v]){
			Tarjan(u,v);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u]){
				cnt++;
				isbridge[id]=1;
			}
		}
		else{
			if(v!=f||flag) 
				low[u]=min(low[u],dfn[v]);
			else flag=1;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>N>>M;
	for(int i=1,u,v;i<=M;i++){
		cin>>u>>v;
		G[u].emplace_back(v,i);
		G[v].emplace_back(u,i);
	}
	for(int i=1;i<=N;i++)
		if(!dfn[i]) Tarjan(0,i);
	cout<<cnt<<'\n';
	for(int i=1;i<=M;i++)
		if(isbridge[i]) cout<<i<<' ';
	return 0;
}

// https://www.luogu.com.cn/problem/U582665

边双连通分量

定义见上。
给出模板代码，以上代码均由 Tarjan\text{Tarjan} 实现。
CPP
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
constexpr int X=5e5+5,Y=2e6+5;

int N,M,cnt;
int dfn[X],low[X],idx;
int st[X],top;
bool instack[X];
vector<pii> G[X];
vector<int> bcc[X];

void Tarjan(int u,int l)
{
	dfn[u]=low[u]=++idx;
	instack[u]=1, st[++top]=u;
	for(pii p:G[u]){
		int v=p.fi, id=p.se;
		if(id==l) continue;
		if(!dfn[v]){
			Tarjan(v,id);
			low[u]=min(low[u],low[v]);
		}
		else if(instack[v]) 
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		cnt++;
		do{
			bcc[cnt].push_back(st[top]);
			instack[st[top]]=0;
		} while(st[top--]!=u);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>N>>M;
	for(int i=1,u,v;i<=M;i++){
		cin>>u>>v;
		if(u==v) continue;
		G[u].emplace_back(v,i);
		G[v].emplace_back(u,i);
	}
	for(int i=1;i<=N;i++)
		if(!dfn[i]) Tarjan(i,0);
	cout<<cnt<<'\n';
	for(int i=1;i<=cnt;i++){
		cout<<bcc[i].size()<<' ';
		for(int u:bcc[i]) cout<<u<<' ';
		cout<<'\n';
	}
	return 0;
}

5.2 有向图的连通性

强连通分量

一个有向图中若点对 u,vu,v 互相可达，则称两点强连通。一个所有点对强连通的极大子图叫做强连通分量。
强连通分量有两种求解算法：Tarjan\text{Tarjan} 和 Kosaraju\text{Kosaraju}。
Tarjan\text{Tarjan} 与上面类似。
Kosaraju\text{Kosaraju} 通过对原图进行 DFS 后序遍历，再按逆序（拓扑序）对反图进行 DFS，最后所有逆 DFS 生成树就是强连通分量。时间复杂度 O(n+m)O(n+m)。

缩点

我们通常要将一个有向图的一个个强连通分量缩成一个点得到一个 DAG，从而更好地对图进行操作。
下面给出由 Tarjan\text{Tarjan} 求 SCC 实现的缩点代码。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=1e4+5;

int N,M,R,res,a[X];
int dfn[X],low[X],scc[X],idx;
int st[X],top;
int w[X],dp[X],in[X];
vector<int> G[X];
vector<int> P[X];

void Tarjan(int u)
{
	dfn[u]=low[u]=++idx;
	st[++top]=u;
	for(int v:G[u]){
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		} 
		else if(!scc[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		R++;
		do scc[st[top]]=R;
		while(st[top--]!=u);
	}
}
queue<int> q;

int Topo()
{
	int res=0;
	for(int i=1;i<=R;i++)
		if(!in[i]) q.push(i);
	while(!q.empty()){
		int u=q.front(); q.pop();
		dp[u]+=w[u];
		for(int v:P[u]){
			dp[v]=max(dp[v],dp[u]);
			in[v]--;
			if(!in[v]) q.push(v);
		}
	}
	for(int i=1;i<=R;i++)
		res=max(res,dp[i]);
	return res;
}

int main()
{
	cin>>N>>M;
	for(int i=1;i<=N;i++) cin>>a[i];
	for(int i=1,u,v;i<=M;i++){
		cin>>u>>v;
		G[u].push_back(v); 
	}
	for(int i=1;i<=N;i++)
		if(!dfn[i]) Tarjan(i);
	for(int u=1;u<=N;u++)
		for(int v:G[u]){
			if(scc[u]==scc[v]) continue;
			P[scc[u]].push_back(scc[v]);
			in[scc[v]]++;
		}
	for(int i=1;i<=N;i++)
		w[scc[i]]+=a[i];
	cout<<Topo();
}
下面是 Kosaraju\text{Kosaraju} 的代码，时间复杂度为 O(n+m)O(n+m)，但由于要做两次 DFS，所以要劣一些。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=1e4+5;

int N,M,a[X],b[X],in[X],f[X];
int scc[X],R,res;
bool vis[X];
vector<int> G[X],rG[X];
vector<int> P[X];
stack<int> st;

void DFS(int u)
{
	vis[u]=1;
	for(int v:G[u])
		if(!vis[v]) DFS(v);
	st.push(u);
}
void rDFS(int u)
{
	scc[u]=R;
	for(int v:rG[u])
		if(!scc[v]) rDFS(v);
}
void Kosaraju()
{
	for(int i=1;i<=N;i++) if(!vis[i]) DFS(i);
	while(!st.empty()){
		int i=st.top(); st.pop();
		if(scc[i]) continue;
		R++; rDFS(i);
	}
}

void Topo()
{
	queue<int> q; 
	for(int i=1;i<=R;i++){
		f[i]=b[i];
		if(!in[i]) q.push(i);
	}
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int v:P[u]){
			f[v]=max(f[v],f[u]+b[v]);
			in[v]--;
			if(!in[v]) q.push(v);
		}
	}
}

int main()
{
	cin>>N>>M;
	for(int i=1;i<=N;i++) cin>>a[i];
	for(int i=1,u,v;i<=M;i++){
		cin>>u>>v;
		G[u].push_back(v);
		rG[v].push_back(u);
	}
	Kosaraju();
	for(int i=1;i<=N;i++){
		b[scc[i]]+=a[i];
		for(int v:G[i]){
			if(scc[i]==scc[v]) continue;
			P[scc[i]].push_back(scc[v]);
			in[scc[v]]++;
		}
	}
	Topo();
	for(int i=1;i<=R;i++)
		res=max(res,f[i]);
	cout<<res;
	return 0;
}

6. 最近公共祖先（LCA）

经典树上问题。求法多种多样。

6.1 倍增法

考虑到暴力求 LCA 的效率太低，因为每次往上跳一步的效率太低。考虑倍增。
定义 fai,jfa_{i,j} 为节点 ii 向上跳 2k2^k 步所到达的节点，不难想到递推式：
fai,j=fafai,j−1,j−1fa_{i,j}=fa_{fa_{i,j-1},j-1}
查询时倍增查找即可，时间复杂度 O((q+n)log⁡n)O((q+n)\log n)。给出代码：
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=5e5+5,Y=20;

int N,M,S,dep[X];
int Lg[X],fa[X][Y];
vector<int> G[X];

void DFS(int f,int u)
{
	fa[u][0]=f, dep[u]=dep[f]+1;
	for(int v:G[u])
		if(v!=f) DFS(u,v);
}
inline int LCA(int u,int v)
{
	if(dep[u]>dep[v]) swap(u,v);
	int f=Lg[dep[u]],g=Lg[dep[v]];
	for(int i=g;~i;i--)
		if(dep[fa[v][i]]>=dep[u])
			v=fa[v][i];
	if(u==v) return u;
	for(int i=f;~i;i--)
		if(fa[u][i]!=fa[v][i])
			u=fa[u][i], v=fa[v][i];
	return fa[u][0];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>N>>M>>S;
	for(int i=1,u,v;i<N;i++){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	DFS(0,S);
	for(int i=2;i<=N;i++) Lg[i]=Lg[i>>1]+1;
	for(int i=1;i<=Lg[N];i++)
		for(int j=1;j<=N;j++)
			fa[j][i]=fa[fa[j][i-1]][i-1];
	while(M--){
		int u,v; cin>>u>>v;
		cout<<LCA(u,v)<<'\n';
	}
}

6.2 Tarjan\text{Tarjan}

把询问离线下来做 DFS，用并查集维护已访问节点，后序遍历树的根即为两者的最近公共祖先。朴素实现平均复杂度为 O(qα(q+n,n)+n)O(q\alpha(q+n,n)+n)。线性的 O(n+q)O(n+q) 做法见论文。
CPP
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
constexpr int X=5e5+5; 

int N,M,S,fa[X],siz[X];
bool vis[X];
vector<int> G[X];

struct query{
	int x,y,ans;
}q[X];
vector<pii> Q[X];

int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}

void Tarjan(int u){
	vis[u]=1;
	for(int v:G[u]){
		if(vis[v]) continue;
		Tarjan(v);
		fa[v]=u;
	}
	for(pii p:Q[u]){
		int v=p.fi, id=p.se;
		if(!vis[v]) continue;
		q[id].ans=find(v);
	}
}

int main()
{
	cin>>N>>M>>S;
	for(int i=1;i<=N;i++) fa[i]=i;
	for(int i=1,a,b;i<N;i++){
		cin>>a>>b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for(int i=1,a,b;i<=M;i++){
		cin>>a>>b;
		Q[a].emplace_back(b,i);
		Q[b].emplace_back(a,i);
	}
	Tarjan(S);
	for(int i=1;i<=M;i++) cout<<q[i].ans<<'\n';
}

6.3 RMQ 解法

记录所有节点的 dfndfn，并转化为 RMQ 问题求解。
下面给出使用 DFS 序求解的方法。当 u=vu=v 时，答案即为 uu，当 u≠vu\neq v 时，设 u,vu,v 的最近公共祖先为 dd，注意到 dd 的至少一个儿子的 dfndfn 会出现在 [dfnu+1,dfnv][dfn_u+1,dfn_v] 中。所以设 u<vu<v，则答案即为 dfndfn 为 [dfnu+1,dfnv][dfn_u+1,dfn_v] 中深度最小的节点的父亲。转化为静态 RMQ 问题求解即可。
一个技巧是直接将节点父亲存在 ST 表最底层。因为在一段连续的 dfndfn 中，若父亲 dfndfn 是最小的，则不存在节点深度比它浅，可以画图去理解。
给出代码实现，O(nlog⁡n)O(n\log n) 预处理，O(1)O(1) 查询，时间复杂度 O(nlog⁡n+q)O(n\log n+q)。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=5e5+5,Y=20;

int N,M,S,idx;
int Lg[X],dfn[X],st[X][Y];
vector<int> G[X];

inline int cmp(int x,int y)
{
	return dfn[x]<dfn[y]? x:y;
}
void DFS(int f,int u)
{
	dfn[u]=++idx;
	st[dfn[u]][0]=f;
	for(int v:G[u])
		if(v!=f) DFS(u,v);
}
inline int LCA(int u,int v)
{
	if(u==v) return u;
	u=dfn[u], v=dfn[v];
	if(u>v) swap(u,v);
	return cmp(st[u+1][Lg[v-u]],st[v-(1<<Lg[v-u])+1][Lg[v-u]]);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>N>>M>>S;
	for(int i=1,u,v;i<N;i++){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	DFS(0,S);
	for(int i=2;i<=N;i++) Lg[i]=Lg[i>>1]+1;
	for(int i=1;i<=Lg[N];i++)
		for(int j=1;j+(1<<i)-1<=N;j++)
			st[j][i]=cmp(st[j][i-1],st[j+(1<<i-1)][i-1]);
	while(M--){
		int u,v; cin>>u>>v;
		cout<<LCA(u,v)<<'\n';
	}
}

6.4 树链剖分解法

详情见下面树剖的部分。
时间复杂度 O(n+mlog⁡n)O(n+m\log n)，且常数极小。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int X=5e5+5;

int N,M,S;
int dep[X],son[X],fa[X];
int siz[X],top[X];
vector<int> G[X];

void DFS1(int f,int u){
	dep[u]=dep[f]+1, fa[u]=f, siz[u]=1;
	for(int v:G[u]){
		if(v==f) continue;
		DFS1(u,v);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v]) son[u]=v;
	}
}
void DFS2(int t,int u){
	top[u]=t; 
	if(!son[u]) return ;
	DFS2(t,son[u]);
	for(int v:G[u])
		if(v!=fa[u]&&v!=son[u]) 
			DFS2(v,v);
}

inline int LCA(int u,int v)
{
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]]) swap(u,v);
		v=fa[top[v]];
	}
	return dep[u]<dep[v]? u:v;
}


signed main()
{
	ios::sync_with_stdio(0);
	cin>>N>>M>>S;
	for(int i=1,u,v;i<N;i++){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	DFS1(0,S); DFS2(S,S);
	while(M--){
		int u,v; cin>>u>>v;
		cout<<LCA(u,v)<<'\n';
	}
}

7. 树链剖分

一种维护树上带权问题的经典方式。
对树进行 DFS，预处理节点信息。称一个节点的重儿子为子树最大的儿子，其他儿子为轻儿子。然后再进行依次 DFS。将树剖成链，链头为每个节点的轻儿子或是根节点，重儿子为除链头以外的节点。每次遍历到一个节点，可以将链向重儿子延展，轻儿子作为一条新链的链头。可以证明任意一个节点到根结点的路径不会跨过超过 O(log⁡n)O(\log n) 条链。
可以发现，一个节点的子树，以及一条链的连续段的 dfndfn 相等，用线段树维护权值，时间复杂度为 O(log⁡n)O(\log n) 或是 O(log⁡2n)O(\log^2 n)。
下面给出模板代码。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int X=1e5+5;

int N,M,R,P,idx,a[X];
int dep[X],siz[X],son[X],fa[X];
int top[X],dfn[X],rnk[X];
vector<int> G[X];

struct SGT{
#define ls i<<1
#define rs i<<1|1
	struct Node{
		int l,r;
		int dat,tag;
	}t[X<<2];
	inline void push_up(int i){
		t[i].dat=t[ls].dat+t[rs].dat;
		t[i].dat%=P;
	}
	inline void add_tag(int i,int x){
		t[i].tag+=x; t[i].tag%=P;
		t[i].dat+=(t[i].r-t[i].l+1)*x;
		t[i].dat%=P;
	}
	inline void push_down(int i){
		if(t[i].tag){
			add_tag(ls,t[i].tag);
			add_tag(rs,t[i].tag);
			t[i].tag=0;
		}
	}
	void build(int i,int L,int R){
		t[i].l=L, t[i].r=R, t[i].tag=0;
		if(L==R){
			t[i].dat=a[rnk[L]]%P;
			return ;
		}
		int Mid=L+R>>1;
		build(ls,L,Mid);
		build(rs,Mid+1,R);
		push_up(i);
	}
	void update(int i,int L,int R,int x){
		if(L<=t[i].l&&t[i].r<=R){
			add_tag(i,x);
			return ;
		}
		push_down(i);
		int Mid=t[i].l+t[i].r>>1;
		if(L<=Mid) update(ls,L,R,x);
		if(R>Mid) update(rs,L,R,x);
		push_up(i);
	}
	int query(int i,int L,int R){
		if(L<=t[i].l&&t[i].r<=R) return t[i].dat;
		push_down(i);
		int Mid=t[i].l+t[i].r>>1, res=0;
		if(L<=Mid) res+=query(ls,L,R);
		if(R>Mid) res+=query(rs,L,R);
		res%=P;
		return res;
	}
#undef ls
#undef rs
}T;

void DFS1(int f,int u){
	dep[u]=dep[f]+1;
	fa[u]=f, siz[u]=1;
	for(int v:G[u]){
		if(v==f) continue;
		DFS1(u,v);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v]) son[u]=v;
	}
}
void DFS2(int t,int u){
	top[u]=t; 
	dfn[u]=++idx, rnk[idx]=u;
	if(!son[u]) return ;
	DFS2(t,son[u]);
	for(int v:G[u]){
		if(v==fa[u]||v==son[u]) continue;
		DFS2(v,v);
	}
}

void update_path(int u,int v,int x){
	x%=P;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		T.update(1,dfn[top[u]],dfn[u],x);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	T.update(1,dfn[u],dfn[v],x);
}
int query_path(int u,int v){
	int res=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		res+=T.query(1,dfn[top[u]],dfn[u]);
		res%=P;
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	res+=T.query(1,dfn[u],dfn[v]);
	res%=P;
	return res;
}
void update_son(int u,int x){
	T.update(1,dfn[u],dfn[u]+siz[u]-1,x);
}
int query_son(int u){
	return T.query(1,dfn[u],dfn[u]+siz[u]-1);
}

signed main()
{
	cin>>N>>M>>R>>P;
	for(int i=1;i<=N;i++) cin>>a[i];
	for(int i=1,u,v;i<N;i++){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	DFS1(0,R); DFS2(R,R);
	T.build(1,1,N);
	for(int i=1,op;i<=M;i++){
		cin>>op;
		switch(op){
			case 1:{
				int x,y,z; cin>>x>>y>>z;
				update_path(x,y,z);
				break;
			}
			case 2:{
				int x,y; cin>>x>>y;
				cout<<query_path(x,y)<<'\n';
				break;
			}
			case 3:{
				int x,z; cin>>x>>z;
				update_son(x,z);
				break;
			}
			case 4:{
				int x; cin>>x;
				cout<<query_son(x)<<'\n';
				break;
			}
		}
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...