学习笔记-图论

YGBC_ · 2025-11-26 22:02:34 · 算法·理论

图论

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

0. 图的存储

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

邻接矩阵

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

邻接表

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

边集数组

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

链式前向星

用类似链表的结构存储每个节点出发的边，与邻接表类似。（似乎可以用 std::list 实现？）

下面是所有存图方式的核心代码：

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

递归实现。每次遍历到一个节点，就递归到下一层进行遍历。

给出两种遍历的算法。

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 （\text{Kahn} 算法）和 DFS。时间复杂度为 O(n+m)。

BFS （\text{Kahn} 算法）实现：

#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 实现：

#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 单源最短路径

\text{Dijkstra}

使用最广泛的最短路算法，适用于求非负边权图的单源最短路径。

每次选择未更新的离起点最近的节点，以它为中转点更新其他节点的最短路径，直到所有节点被更新。

共更新 n 轮，每轮更新节点 O(n)，总共松弛 O(m) 次路径，所以朴素实现的时间复杂度为 O(n^2+m)=O(n^2)。

下面是朴素实现的代码：

#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(m) 松弛操作，优先队列实现的复杂度为 O((m+n)\log m)=O(m\log m)，若使用能够 O(1) Decrease_key 操作的二叉堆或是线段树，复杂度为 O(m\log n)，斐波那契堆能将复杂度进一步优化为 O(n\log n+m)，但这些做法实际并不一定跑得更快。

下面给出优先队列实现的 \text{Dijkstra}。

#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;
}

\text{Bellman-Ford}

由队列优化的 \text{Bellman-Ford}，其实现方式是将每一轮被松驰过的节点去松弛其他节点。其在随机图中的表现十分优秀，与 \text{Dijkstra} 相当，但其最坏复杂度仍是 O(nm)。

下面给出 \text{SPFA} 的代码实现。

#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 全源最短路径

\text{Floyd}

全名 \text{Floyd-Warshell}，使用较多的全源最短路径算法。

其本质是动态规划算法，设 f_{k,i,j} 为松弛到 k 点，i\rightarrow j 的最短路径，则有转移式如下：

显然这个转移为 O(1)，状态数 O(n^3)，所以 \text{Floyd} 的复杂度为 O(n^3)。

下面给出 \text{Floyd} 的实现代码，实际实现中常常在原邻接矩阵中转移。

#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;
}

\text{Johnson}

一种在稠密图比 \text{Floyd} 更优的全员最短路径算法。其本质是做 n 次 \text{Dijkstra}，但是可以处理负边权。

算法的核心是建立一个源点 0，并向每一个节点建立一条边权为 0的负权边，从此源点开始做一遍 \text{Bellman-Ford}，记 h_u 为从 0 节点到点 u 的最短路径。然后将原图的每条边（从 u 到 v，边权为 w）的边权改为 h_u-h_v+w。然后跑 n 次 \text{Dijkstra} 即可。

注意最后的的路径 dis_{i,j} 要修改为 dis_{i,j}-h_i+h_j。

一种按边贪心的求最小生成树算法。先将边排序，然后从小到大选边，若边的两端节点已经联通就跳过。最后得到的就是最小生成树。

排序复杂度为 O(m\log m)，并查集复杂度为 O(m\log n) 或 O(m\alpha(n))。总时间复杂度为 O(m\log m) ，瓶颈在于排序，所以常数极小。

给出代码实现，注意要特判不连通的情况。

#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; 
}

\text{Prim}

一个多源增广的最小生成树算法，较为冷门。

初始时将每个点当作一个连通块，并遍历边集数组，寻找每个连通块向外最短的边，并将这些边加入最小生成树中。

由于每次连通块数量至少减半，所以最多更新 O(\log n) 次，每次遍历边集数组并使用并查集维护连通块，所以单次迭代复杂度为 O(m\alpha(n)) 所以总时间复杂度为 O(m\alpha(n)\log n)。

下面给出代码。注意边权可能相等，所以连通块之间可能构成环，所以要使用第二关键字对同边权的边进行明确比较，可使用边的编号。

#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;
} 

K 短路问题

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int X=1e5+5;

int N,M,K;
int times[X],dis[X],inq[X],lgst[X];

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

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

void work(int s)
{
    memset(dis,0x3f,sizeof dis);
    q.emplace(s,0);
    while(q.empty()){
        Node n=q.top(); 
        q.pop(); inq[n.u]--; 
        if(times[n.u]==K) continue;
        times[n.u]++; dis[n.u]=d;
        for(Edge e:G[n.u]){
            if(times[n.v]==K) continue;
            if(inq[u.v]>=K&&n.d+e.w>lgst[n.v]) continue;
            q.emplace(n.v,n.d+e.w);
            inq[n.v]++; lgst[n.v]-max(lgst[n.v],n.d+e.w);
        }
    }
}

signed main()
{
    cin>>N>
} 

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

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

5.1 无向图的连通性

割点

在无向图中，若一个点被删去，图中的连通分量数增加了，则这个点为割点。

下面给出 \text{Tarjan} 算法求割点的代码。

#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)。

给出模板代码。

#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;
}

割边

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。

给出代码。

#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

边双连通分量

定义见上。

给出模板代码，以上代码均由 \text{Tarjan} 实现。

#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,v 互相可达，则称两点强连通。一个所有点对强连通的极大子图叫做强连通分量。

强连通分量有两种求解算法：\text{Tarjan} 和 \text{Kosaraju}。

把询问离线下来做 DFS，用并查集维护已访问节点，后序遍历树的根即为两者的最近公共祖先。朴素实现平均复杂度为 O(q\alpha(q+n,n)+n)。线性的 O(n+q) 做法见论文。

#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 解法

记录所有节点的 dfn，并转化为 RMQ 问题求解。

下面给出使用 DFS 序求解的方法。当 u=v 时，答案即为 u，当 u\neq v 时，设 u,v 的最近公共祖先为 d，注意到 d 的至少一个儿子的 dfn 会出现在 [dfn_u+1,dfn_v] 中。所以设 u<v，则答案即为 dfn 为 [dfn_u+1,dfn_v] 中深度最小的节点的父亲。转化为静态 RMQ 问题求解即可。

一个技巧是直接将节点父亲存在 ST 表最底层。因为在一段连续的 dfn 中，若父亲 dfn 是最小的，则不存在节点深度比它浅，可以画图去理解。

给出代码实现，O(n\log n) 预处理，O(1) 查询，时间复杂度 O(n\log n+q)。

#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+m\log n)，且常数极小。

#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) 条链。

可以发现，一个节点的子树，以及一条链的连续段的 dfn 相等，用线段树维护权值，时间复杂度为 O(\log n) 或是 O(\log^2 n)。

下面给出模板代码。

#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;
            }
        }
    }
}