图的储存

1.邻接矩阵

使用条件：适合点数比较少的,注意处理重边时需取 $\min$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int MAXN = 1005; // 最大顶点数
const int INF = 0x3f3f3f3f; // 无穷大
int g[MAXN][MAXN]; // g[u][v] 存储 u 到 v 的边权
int n, m; // n个点，m条边
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v]=min( g[u][v], w ); // 防止重边，取最小权
	    g[v][u]=min( g[v][u], w );// 如果是无向图，加上这一行
    }
    return 0;
}

P2245 星际导航 - 洛谷

2.邻接表

适合大部分场景，简单易懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Edge{ 
	int v;ll w;
}
const int N = 100005; // 节点数量
vector<Edge> adj[N];   // 邻接表
// 加边函数
void add_edge(int u, int v,int w) {
    adj[u].push_back({v,w});
    adj[v].push_back({u,w}); // 如果是无向图，两边都要加
}
// 遍历
for(auto [v,w]:adj[u])
{
}

Trick：$O(1)$ 取反向边？ 在网络流或一些无向图博弈问题中，我们常常需要通过一条有向边 $u \to v$ 快速找到对应的反向边 $v \to u$。
实现：在结构体中额外记录一个 rev 变量，存储反向边在目标节点 vector 中的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Edge{ 
	int v;ll w;
	int rev;
}
const int N = 100005; // 节点数量
vector<Edge> adj[N];   // 邻接表
// 加边函数
void add_edge(int u, int v,int w) {
    adj[u].push_back({v,w,(int)adj[v].size()});
    adj[v].push_back({u,w,(int)adj[u].size()-1}); // 如果是无向图，两边都要加
}
// 遍历与反向边修改演示 ( 以网络流增广为例 )
void update_residual( int u, int edge_idx, ll flow ) {
    auto& [v, w, rev] = adj[u][edge_idx];
    w -= flow;                  // 正向边流量减
    adj[v][rev].w += flow;      // 反向边流量加 (通过 rev 实现 O(1) 索引)
}

3.链式前向星

揪葡萄
想象一下，每个节点（比如节点 1）手里都只能攥住一根绳子。

  • head[u]：就是节点 u 手里攥着的那根绳子的编号。
  • next：每一条边（葡萄）下面都挂着下一条边（葡萄）的编号。
    当我们想找节点 1 连接的所有边时，我们先看它手里攥着哪根（head[1]），顺着这根绳子往下找，直到绳子断了（-1）。
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
const int maxn = 1e5 + 5;
const int maxm = 2e5 + 10;

struct Edge {
    int v, nxt; ll w;
    // 目标 | 下一条边 | 边权
} edge[maxm];
int head[maxn], tot;

void init( ) {
    memset( head, -1, sizeof head );
    tot = 0;
}

void add_edge( int u, int v, ll w ) {
    edge[tot] = { v, w, head[u] };
    head[u] = tot ++;
}

void search( int u ) {
    for( int i = head[u]; i != -1; i = edge[i].nxt ) {
        int v = edge[i].v; ll w = edge[i].w;
        cout << u << " -> " << v << " (" << w << ")" << '\n';
    }
}

// 插入一对正反向边（网络流初始化）
void add_flow_edge( int u, int v, ll cap ) {
    add_edge( u, v, cap ); // 正向边，编号为 cnt
    add_edge( v, u, 0 );   // 反向边，编号为 cnt ^ 1
}

// 残量网络更新演示 (不再需要额外的 rev 变量)
void update_residual( int edge_idx, ll flow ) {
    edge[edge_idx].w -= flow;     // 正向边减流量
    edge[edge_idx ^ 1].w += flow; // 反向边加流量 (通过异或 O(1) 直接定位)
}

4.只有边的数组(Kruskal 算法时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Edge {
    int u, v, w;
    // 重载 < 运算符，方便 sort 排序
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
} ;
// 使用数组存储  
Edge edges[MAXM];
int edge_count = 0; 
// 加边函数 
void add_edge(int u, int v, int w) 
{ edges[edge_count++] = {u, v, w}; }
// 使用时直接 sort(edges, edges + m);

对比

方式 空间 遍历效率 查边效率 $u \to v$ 适用场景
直接存边 $O(E)$ $O(E)$ $O(E)$ 无固定遍历起点，需对整体边集进行排序与遍历（如 Kruskal 算法）。
邻接矩阵 $O(V^2)$ $O(V)$ $O(1)$ 点数少 ($N \le 500$)，边稠密，需频繁判断连通。
邻接表 $O(E)$ $O(deg(u))$ $O(deg(u))$ 大部分情况通用，代码最简洁，易于拓展。
链式前向星 $O(E)$ $O(deg(u))$ $O(deg(u))$ 常数极小，方便维护反向边、边编号。

图的遍历

这里代码都使用邻接表

DFS

依赖递归实现，直到无路可走再回溯

1
2
3
4
5
6
7
8
9
vector<int> adj[N]; // 邻接表
vector<bool> vis;         // 记录节点是否已经遍历

void dfs(int u) {
	vis[u] = true;
	cout<<u<<" ";
	for (int v : adj[u])
	if (!vis[v]) dfs(v)
}

BFS

依赖队列实现，一层一层搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> adj[N];   // 邻接表
vector<bool> vis;         // 记录节点是否已经遍历
int n;
void bfs(int s) 
{
    queue<int> q;
    vis[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";

        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

拓扑排序

特点：使得对于图中的任意一条有向边 (u -> v)，在排序结果中 u 总是出现在 v 的前面
时间复杂度：$O(V+E)$
注意：1.拓扑排序的结果不一定唯一，只要有多个顶点的入度同时为 0，谁先被访问都可以
2.有环无法进行拓扑排序
3.它不是传统意义上的数值排序，而是一种偏序关系的线性化

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
int ind[N],n;//ind是入度的数量
vector <int> adj[N],tp;
bool topo()
{
	queue<int> q;
	for(int i=1;i<=n;++i)
	{
		if(ind[i]==0) q.push(i);
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		//记录
		tp.push_back(u);
		for(int v:adj[u])
		{
			ind[v]--;
			if(ind[v]==0) q.push(v);
		}
	}
	return tp.size()==n;	
}
//输出排序
for(auto x:tp) printf("%d ",x);

最小生成树

1.Prim

朴素版

时间复杂度：$O(V^2)$
核心操作：每次都要遍历所有顶点，去寻找距离集合最近的那个未访问顶点

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
const int INF = 0x3f3f3f3f;
struct Edge { 
	int v; ll w; 
};
vector<Edge> adj[N]; // 邻接表
int dis[N];       // 点到生成树的距离
bool vis[N];        // 是否已在树中
int prim(int V) {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    ll ans = 0;
    int cnt = 0;
    for (int i = 1; i <=V; i++) {
        int t = -1;
        // 1. 暴力遍历：找当前不在树中且距离树最近的点 t
        for (int j = 1; j <= V; j++) {
            if (!vis[j] && (t == -1 || dis[t] > dis[j])) {
                t = j;
            }
        }
        // 检查连通性
        if (t==-1||dis[t] == INF) return INF;
        // 2. 统计结果
        ans += dis[t];
        vis[t] = true;
        cnt++;
        // 3. 用新加入的点 t 更新它的邻居到树的距离
        for (auto [v,w]: adj[t]) {
            if (!vis[v] && dis[v] > w) {
                dis[v] = w;
            }
        }
    }
    return (cnt == V) ? ans : -1;
}

堆优化版

时间复杂度：$O(Elog V)$
核心操作：把所有可用的边扔进一个最小堆（优先队列)中,每次直接从堆顶弹出当前权值最小的边，取出顶点

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
const int INF = 0x3f3f3f3f;
struct Edge {
    int v; ll w;
};
struct State {
    int u; ll d;
    // 优先队列维护小根堆
    bool operator < (const State& oth) const { return d > oth.d; }
};
vector<Edge> adj[N]; // 邻接表
ll dis[N];       // 点到生成树的距
bool vis[N];        // 是否已在树中
  
int prim() {
    fill( dis + 1, dis + V + 1, inf );
    fill( vis + 1, vis + V + 1, false );
    priority_queue<State> pq;
    dis[1] = 0;
    q.push({1,0});
    ll ans = 0; // 总权重
    int cnt = 0; // 进树的点数
    while (!pq.empty()) {
        auto [u,d]=pq.top();
        pq.pop();
        if (vis[u]) continue; // 冗余点处理
        vis[u] = true;
        ans += d;
        cnt++;
        // 遍历 u 的所有邻居
        for( auto [v, w] : adj[u] ) {
            if( !vis[v] && w < dis[v] ) {
                dis[v] = w;
                pq.push({ v, dis[v]});
            }
        }
    }
    return (cnt == n) ? ans : INF;

}

2.Kruskal

时间复杂度：$O(ElogE)$
核心操作:使用并查集，对于每一条边，判断其两端点是否连通。

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
// 定义边的结构体
struct Edge {
    int u, v;ll w;
    // 重载 < 运算符，用于 sort(也可以写一个cmp比较函数)
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
}edg[N];
int fa[N],ans,cnt;
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
ll kruskal(int V)
{ 
	sort(edg,edg+m);//m是边数，n是点数
	for(int i=1;i<=n;++i)
	{
		fa[i]=i;
	}
    for( auto [u, v, w] : edg ) {
        int ru = find( u ), rv = find( v );
        if( ru != rv ) {
            fa[ru] = rv;
            ans += w; cnt ++;
            // 若需要构建 MST 的树结构，可在此处连边: adj[u].push_back({v, w});
            if( cnt == V - 1 ) break;
        }
    }
    
    if( cnt < V - 1 ) return -1; // 图不连通，无法构成生成树
    return ans;
}

虚拟源点

常见题面线索：

  • 有若干台机器/基站/集群，彼此连线有代价 w(u,v)
  • 还必须把它们接到“电网/水源/上级网络/主站”，而主站本身不在原图中，或者接主站的代价不是统一的边，而是一个接入成本；
    建图方式：建立一个超级源点（虚拟源点 $0$）。将所有“点权”转化为该点到超级源点 $0$ 的“边权”。然后对包括 $0$ 号点在内的 $V+1$ 个点跑一次普通的最小生成树。

严格次小生成树

算法的核心思想是“换边”：

  1. 先用 Kruskal 算法求出最小生成树，记录其权值总和为 sum。
  2. 遍历每一条不在最小生成树中的非树边 $e(u, v, w)$。如果把这条边强行加到树中，树上就会形成一个环（即 $u$ 到 $v$ 的树上路径加上这条新边）。
  3. 为了重新变成一棵树，我们需要在这个环里删掉一条原本就在树上的边。
  4. 为了让新的树权值总和增加得最少（且严格大于 sum），我们需要在 $u$ 到 $v$ 的树上路径中，找到权值最大、且严格小于 $w$ 的那条树边替换掉。
    洛谷P4180
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=3e5+5,inf=2e9;
struct Edge{
    int u,v,w;
    bool vis;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};
struct Edge1{
    int v,w;
};
int fa[N];
int find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
vector<Edge1> adj[N];
int up[N][20],dep[N],w1[N][20],w2[N][20];
Edge edg[M];
ll sum=0;
int n,m;
void kru()
{    
    int cnt=0;
    sort(edg,edg+m);
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=0;i<m;++i)
    {
        auto& [u,v,w,vis]=edg[i];
        int ru=find(u),rv=find(v);
        if(ru!=rv)
        {
            fa[ru]=rv;
            cnt++;
            sum+=w;
            vis=1;
            adj[v].push_back({u,w});
            adj[u].push_back({v,w});
            if(cnt==n-1) break;
        }
        else vis=0;
    }
}
void dfs(int u,int p,int ww)
{
    dep[u]=dep[p]+1;
    up[u][0]=p;
    w1[u][0]=ww,w2[u][0]=-inf;
    for(int i=1;i<=19;++i)
    {
        up[u][i]=up[up[u][i-1]][i-1];
        w1[u][i]=max(w1[u][i-1],w1[up[u][i-1]][i-1]);
        w2[u][i]=max(w2[u][i-1],w2[up[u][i-1]][i-1]);
        if(w1[u][i-1]!=w1[up[u][i-1]][i-1])
        {
            w2[u][i]=max(w2[u][i],min(w1[u][i-1],w1[up[u][i-1]][i-1]));
        }
    }
    for(auto [vv,ww]:adj[u])
    {
        if(vv==p) continue;
        dfs(vv,u,ww);
    }
}
int lca(int u,int v)
{
    if(dep[v]>dep[u]) swap(u,v);
    for(int i=19;i>=0;--i)
    {
        if(dep[up[u][i]]>=dep[v])
        {
            u=up[u][i];
        }
    }
    if(u==v)
    {
        return u;
    }
    for(int i=19;i>=0;--i)
    {
        if(up[u][i]!=up[v][i])
        {
            u=up[u][i];
            v=up[v][i];
        }
    }
    return up[u][0];
}
int F(int u,int v,int w)
{
    int res=-inf;
    int l=lca(u,v);
    for(int i=19;i>=0;--i)
    {
        if(up[u][i]&&dep[up[u][i]]>=dep[l])
        {
            if(w1[u][i]<w)
            {
                res=max(res,w1[u][i]);
            }
            else res=max(res,w2[u][i]);
            u=up[u][i];
        }
    }
    for(int i=19;i>=0;--i)
    {
        if(up[v][i]&&dep[up[v][i]]>=dep[l])
        {
            if(w1[v][i]<w)
            {
                res=max(res,w1[v][i]);
            }
            else res=max(res,w2[v][i]);
            v=up[v][i];
        }
    }
    return res;
}
void solve() 
{
    cin>>n>>m;
    for(int i=0;i<m;++i)
    {
        int x,y,z;
        cin>>x>>y>>z;
        edg[i]={x,y,z};
    }
    kru();
    dfs(1,0,-inf);
    ll ans=1e18;
    for(int i=0;i<m;++i)
    {
        auto [u,v,w,vis]=edg[i];
        if(!vis&&u!=v)
        {
            int val=F(u,v,w);
            if(val>-inf)
            {
                ans=min(ans,sum-val+w);
            }
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

最短路问题

最短路

1.Dijkstra

特点：单源 非负边

朴素版

时间复杂度：$O(V^2)$
核心操作:每一轮都需要遍历所有顶点，找到距离起点最近的一个,并更新其邻居距离

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
const int N=1e4+5;
const int INF = 0x3f3f3f3f;
vector<int> adj[N];
int n;
void dijkstra(int st) 
{
    vector<int> dis(n + 1, INF);    // 距离
    vector<bool> vis(n + 1, false); // 是否已确定
    dis[st] = 0;
    for (int i = 0; i < n; i++) {
        // 1. 找当前未访问中距离最小的点 t
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (t == -1 || dis[j] < dis[t])) {
                t = j;
            }
        }
        // 没有可达点
        if (dis[t] == INF) break;
        // 2. 标记
        vis[t] = true;
        // 3. 更新
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && adj[t][j] < INF) {
                dis[j] = min(dis[j], dis[t] + adj[t][j]);
            }
        }
    }
}

堆优化版

时间复杂度：$O(ElogE)$
核心操作:使用最小堆（优先队列）存储 (距离, 顶点)对

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
struct Edge {
    int v;
    ll w;  
};
struct State { // State 状态
    int u; ll d;
    bool operator < (const State& oth) const { return d > oth.d; }
};
vector<Edge> adj[N];
int n;
void dijkstra_heap(int st) {
    // 初始化
    vector<int> dis(n + 1, INF);
    vector<bool> vis(n + 1, false);
    dis[st] = 0;
    priority_queue< State > pq;
    dis[S] = 0; 
    pq.push({ S, 0 });
    while( !pq.empty( ) ) {
        auto [u, d] = pq.top(); pq.pop();
        // 剪枝：若当前的距离已经不是最优，直接跳过
        if(vis[u]) continue;
        vis[u]=1;
        if( d > dist[u] ) continue;
        for( auto& [v, w] : adj[u] ) {
            if( dis[v] > dis[u] + w ) {
                dis[v] = dis[u] + w;
                pq.push({ v, dis[v] });
            }
        }
    }
}

2.Bellman-ford

特点：单源 负边
时间复杂度：$O(VE)$
核心操作:需要对所有顶点进行松弛,每一轮都需要遍历图中的所有边，对每条边执行松弛操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Edge { int u, v, w; };
vector< Edge > edges;
ll dis[N];
int n, m, s;

bool bellman_ford( int S )  {
    fill( dist, dist + n + 1, inf );
    dis[S] = 0;
    bool relaxed;
    for( int i = 1; i <= n; ++ i ) {
        relaxed = false;
        for( auto &[u, v, w] : edges ) {
            if( dis[u] != inf && dis[u] + w < dis[v] ) {
                dis[v] = dis[u] + w;
                relaxed = true;
                if( i == n ) return true;
            }
        }
        if( !relaxed ) break;
    }
    return false;
}

3.Spfa

特点：负 单源
Bellman-Ford 算法的队列优化版本。
时间复杂度：$O(E)$~$O(VE)$
核心操作：只有那些在前一轮被成功松弛的顶点，才有可能引起下一轮的距离更新。因此，用一个队列来维护这些“待松弛”的顶点，避免了 Bellman-Ford 那种盲目的全局遍历。

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
const int N=100,inf=0x3f3f3f3f;
struct Edge{
	int v;ll w;
};
vector <Egde> adj[N];
ll dis[N];
bool inq[N]; // 是否在队列中
int cnt[N];  // 节点入队次数，用于判负环

// 返回值为是否存在负环
bool spfa( int s, int n ) {
	fill( dist + 1, dis + N + 1, inf );
	fill( cnt + 1, cnt + N + 1, 0 );
	fill( inq + 1, inq + N + 1, false );
    
	queue<int> q; dis[s] = 0;
	q.push(s); inq[s] = true;
    
	while( !q.empty() ) {
	    int u = q.front(); q.pop( );
	    inq[u] = false;
        
	    for( auto& [v, w] : adj[u]) {
			if( dis[v] > dis[u] + w ) {
				dis[v] = dis[u] + w;
				cnt[v] = cnt[u] + 1;
				if( cnt[v] >= N ) return true; // 存在负环
				if( !inq[v] ) q.push(v), inq[v] = true;
			}
		}
    }
    return false; // 无负环
}

4.Floyd

特点： 全源 负边
时间复杂度：$O(V^3)$ 适合n比较小的
核心操作：从 i到 j的最短路径，要么不经过顶点 k（保持原样），要么经过顶点 k（拆分成两段：$i \to k$和$k \to j$）。本质是动态规划

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
const int N=205,inf=0x3f3f3f3f;
int d[N][N];//d初始化为inf
int n,m;
void init()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(i==j) d[i][j]=0;
            else d[i][j]=inf;
        }
    }
}
void floyd()
{
    for(int k=1;k<=n;++k)
    {
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
            }
        }
    }
}

floyd还可以查看两点是否连通

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//d[][]初始化为0，有边为1
void floyd()
{
    for(int k=1;k<=n;++k)
    {
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                d[i][j]|=(d[i][k]&d[k][j]);
            }
        }
    }
}

差分约束

一种将代数不等式组转化为图论最短路/最长路问题的技巧
处理Xv-Xu​≤w 的不等式

  • 移项：Xv​≤Xu​+w
  • 映射：将变量 Xv​ 看作图中的节点 v。
  • 建边： 上式完美契合三角形不等式（最短路松弛条件），连一条 u→v 的权值为 w 的边。
    最后我们跑一遍Spfa即可，没有负环说明有解
不等式 建边方式
Xv−Xu​≤w​ 连边 u→v，权值为 w
Xu−Xv​≥w​ 连边 u→v，权值为 -w
Xu−Xv​=w​ 连边 u→v和 v→u，权值均为 w

次短路

在一个赋权图中，路径长度仅次于最短路的路径。次短路问题通常分为两种严格定义：

  1. 严格次短路：路径长度严格大于最短路（$\text{长度} > \text{最短路长度}$）。

  2. 非严格次短路：路径长度大于或等于最短路，但不能是同一条路径（允许长度相等，通常用于寻找前 $K$ 条最短路）。

方法：
我们在经典的 Dijkstra 算法基础上，为每个节点维护两个状态：

  • dis1[i]：从源点到节点 $i$ 的最短距离。

  • dis2[i]：从源点到节点 $i$ 的次短距离。

更新逻辑：

当我们在松弛一条边 $u \to v$（权值为 $w$）时，尝试用 $D = dist[u] + w$ 去更新 $v$ 的状态。更新时会遇到以下三种情况：

  1. $D < dis1[v]$：发现了更短的最短路。原最短路退化为次短路（dis2[v] = dis1[v]），然后更新最短路（dist1[v] = D）。两者的节点都入队。

  2. $dis1[v] < D < dis2[v]$：$D$ 夹在最短路和次短路之间。直接更新次短路（dis2[v] = D），并将更新后的状态入队。

  3. $D == dis1[v]$：（针对非严格次短路）如果不要求严格大于，可以丢弃或计入计数；如果是严格次短路，则不操作。

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
void dij(int s)
{
	vector<int> dis1(n + 1, INF); // 最短路
    vector<int> dis2(n + 1, INF); // 次短路
	priority_queue<State> pq;
    dis1[s] = 0;
    pq.push({s, 0});
    while (!pq.empty()) {
        auto [u,d] = pq.top();
        pq.pop();
        // 如果当前弹出的距离已经比已知的次短路还要大，直接剪枝
        if (d > dis2[u]) continue;
        
        for (auto&[v,w]: adj[u]) {
            int nextd = d + w;
            
            // 情况 1：可以更新最短路
            if (next_d < dis1[v]) {
                dis2[v] = dis1[v]; // 原最短路退化为次短路
                dis1[v] = nextd;   // 更新最短路
                pq.push({v, dis1[v]});
                pq.push({v, dis2[v]});
            }
            // 情况 2：大于最短路，但可以更新次短路（保证严格次短路）
            else if (nextd > dis1[v] && nextd < dis2[v]) {
                dis2[v] = nextd;   // 更新次短路
                pq.push({v, dis2[v]});
            }
        }
    }
}

分层最短路

应用场景

在求最短路时，题目增加了一些动态的“硬性限制条件”或“特殊操作机会”。
比如：

  • 有 $k$ 次机会让某条边的边权变为 0（免路费）。
  • 有 $k$ 次机会让某条边的边权减半（如你上一题的代码）。
  • 必须经过恰好某几个特定的点，或满足某种特定的状态切换。

核心思想

将原图复制成k+1层（或更多），每一层代表一种状态，通过在层与层之间建立特殊的转移边来模拟状态的切换。
假设原图有 $n$ 个点，$m$ 条边，你拥有 $k$ 次“特殊机会”。我们就会建立一个包含 $k+1$ 层的图：

  • 第 0 层：原图的完整复制，表示一次机会都还没用的状态。
  • 第 1 层：原图的完整复制，表示已经用掉 1 次机会的状态。
  • ……
  • 第 $k$ 层：原图的完整复制，表示 $k$ 次机会已经全部用完的状态。

边

分层图中的边分为两种：同层边 和 跨层边

同层边（不使用特殊机会）

在每一层内部，原图有的边，这一层也要照搬连上，而且边权不变。

  • 数学表达：如果原图中 $u$ 到 $v$ 有一条权值为 $w$ 的边，那么在第 $j$ 层内部，就要连一条 (u + j*n) 到 (v + j*n)、权值为 $w$ 的边。

  • 物理含义：你从 $u$ 走到 $v$，但你决定不使用特殊机会。既然没用机会，你耗费的代价就是原价 $w$，并且你所处的层数（状态）不会改变。

跨层边（使用特殊机会）

这是分层图的灵魂。我们要从低楼层向高楼层连一条单向斜线边。

  • 数学表达：如果原图中 $u$ 到 $v$ 的边权为 $w$，且你可以通过使用一次机会让边权变成 $w'$（比如免费就是 0，减半就是 $w/2$），那么就要从第 $j$ 层的 $u$ 连一条单向指向第 $j+1$ 层的 $v$、权值为 $w'$ 的边。即 (u + j*n) $\to$ (v + (j+1)*n)。

  • 物理含义：你从 $u$ 走到 $v$ 的同时，决定消耗一次特殊机会。因为用了机会，这条边的代价变成了特价 $w'$；同时由于机会次数加 1，你的状态发生了改变，从第 $j$ 层“上升”到了第 $j+1$ 层

示例代码

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
struct Edge{
	int v;ll w; 
};
int n,m;
vector<Edge> adj[N];
void solve()
{
	cin>>n>>m>>k;
	for(int i=0;i<m;++i)
	{
		int x,y,z;
		cin>>x>>y>>z;
		for(int j=0;j<=k;++j)
		{
			adj[x+j*n].push_back({y+j*n,z});
			adj[y+j*n].push_back({x+j*n,z});
			if(j!=k)
			{
				adj[x+j*n].push_back({y+(j+1)*n,z/2});
				adj[y+j*n].push_back({x+(j+1)*n,z/2});
			}
		}	
	}
	int ans=inf;
	for(int i=0;i<=k;++i)
	{
		ans=min(ans,dis[t+i*n]);
	}
	cout<<ans<<endl;
}

同余最短路

适用问题：给定n个可重复使用的整数，求能拼凑出的数量、无法拼凑的最大/最小数、模K余p的最小拼凑数
方法：
1.找到最小的数 x ，然后根据取余得到 （0,1,...x-1），将这些数看作点
2.然后遍历其他的数 a[i]，进行
for(int j=0;j<x;++j)
{
e[j].push_back({(j+a[i])%x,a[i]});
}
加边
3.最后进行最短路即可

能不能凑出数值 X？

  • 计算 r=X%amin​。
  • 如果 dis[r] <= X，说明可以凑出！因为你可以通过不断地加 amin​（这不会改变余数），把 dis[r]刚好提升到 X。
  • 如果 dis[r] == X，说明 X本身就是达到该余数的最小代价。

洛谷P5020

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
const int N=25005,inf=0x3f3f3f3f;
struct Edge{
	int v,w;
};
vector <Edge> adj[N];
int n,a[105],vis[N],dis[N],x,tr[N];
void spfa()
{
	queue<int> q;
	for(int i=0;i<x;++i)
	{
		dis[i]=inf,vis[i]=0,tr[i]=0;
	}
	dis[0]=0,vis[0]=1;
	q.push(0);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto ed:adj[u])
		{
			int v=ed.v,w=ed.w;
			if(dis[v]>w+dis[u])
			{
				dis[v]=dis[u]+w;
				tr[v]=w;
				if(vis[v]==0) 
				{
					vis[v]=1;
					q.push(v);
				}
			}else if(dis[v]==dis[u]+w&&tr[v]>w)
			{
				tr[v]=w;
			}
		}
	}
	set<int> st;
	for(int i=0;i<x;++i)
	{
		st.insert(tr[i]);
	}
	cout<<st.size()<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;++i) cin>>a[i];
		sort(a+1,a+n+1);
		x=a[1];
		for(int i=0;i<x;++i)
		{
			adj[i].clear();
		}
		for(int i=2;i<=n;++i)
		{
			for(int j=0;j<x;++j)
			{
				adj[j].push_back({(j+a[i])%x,a[i]});
			}
		}
		spfa();
	}
	return 0;
}

二分图

通俗来说：如果能把一个图里的所有顶点分成两个独立的集合（设为 A 组和 B 组），使得每一条边连接的两个顶点都分别属于这两个不同的集合（即 A 组内部的点没有边相连，B 组内部的点也没有边相连），那么这个图就叫二分图
性质：二分图不含奇数环

二分图判定 (染色法）

从任意一个点开始染黑色，那它所有相邻的点就必须染白色。以此类推，扩散全图。如果在染色的过程中，发现某个点和它相邻的点被染成了同一种颜色，说明图里有奇环，它就不是二分图。

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
const int N = 100005;
vector<int> adj[N]; // 邻接表存图
int color[N];     // 0:未染色, 1:黑色, 2:白色

// 返回 true 表示是二分图，false 表示不是
bool bfs_check(int s) {
    queue<int> q;
    q.push(s);
    color[s] = 1; // 初始点染黑色
    
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        
        for(int v : adj[u]) {
            if(color[v] == 0) { // 如果邻居没染色
                color[v] = 3 - color[u]; // 1变2, 2变1 (染成相反的颜色)
                q.push(v);
            } else if(color[v] == color[u]) {
                // 如果邻居已经染了色，且和当前点颜色一样，说明冲突了（存在奇环）
                return false; 
            }
        }
    }
    return true;
}
//调用
bool is_bipartite = true;
for(int i = 1; i <= n; ++i) {
    if(color[i] == 0) { // 处理图不连通的情况
        if(!bfs_check(i)) {
            is_bipartite = false;
            break;
         }
    }
}

二分图的最大匹配（匈牙利算法）

它的核心思想就是经典的“月老牵线，不行就拆散重组（寻找增广路）”：

  1. 帮 A 组的男 1 号找 B 组的心仪对象。如果姑娘没许配人，直接牵线。
  2. 如果姑娘已经许配给男 2 号了，月老就会去问男 2 号：“哥们，能不能把你媳妇让出来，我重新帮你物色一个？”
  3. 如果男 2 号真的找到了备胎，那他就把前妻让给男 1 号。匹配数成功 $+1$。
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
const int maxv = 1050;
vector<int> adj[maxv]; // 左部点连接的右部点
int match[maxv];       // match[i] = j 表示右部点 i 当前匹配的是左部点 j
bool vis[maxv];        // 右部点在这一轮是否被访问过（避免死循环）
// 寻找从 u 出发的增广路
bool dfs( int u ) {
    for( int v : adj[u] ) {
        if( vis[v] ) continue;
        vis[v] = 1;
        // 如果右部点 v 还是单身，或者 v 的现任 match[v] 能够找到下家
        if( match[v] == -1 || dfs( match[v] ) ) {
            match[v] = u;
            return 1;
        }
    }
    return 0;
}
int hungarian( int n ) {
    int ans = 0;
    memset( match, -1, sizeof( match ) );
    for( int i = 1; i <= n; ++ i ) {
        memset( vis, 0, sizeof( vis ) ); 
        // 每一轮每个左部点都要重置访问标记
        if( dfs( i ) ) ans ++;
    }
    return ans;
}

连通分量

特性 强连通分量 (SCC) 弱连通分量 (WCC)
路径要求 必须有双向有向路径 仅要求有无向连接
方向敏感性 严格遵守箭头方向 忽略箭头方向
经典算法 Tarjan 算法、Kosaraju 算法 并查集 (DSU)、BFS/DFS
应用场景 寻找环、缩点转化 DAG、解决 2-SAT 问题 社交网络群体划分、基础连通性分析

1. 强连通分量 (SCC)

定义：
在一个有向图的子图中，如果任意两个顶点 $u$ 和 $v$ 之间都存在双向路径（即既有从 $u$ 到 $v$ 的路径，也有从 $v$ 到 $u$ 的路径），那么这个子图被称为是强连通的。一个图的最大强连通子图就称为强连通分量。

  • 直观理解：在这个分量内部，你可以从任何一个点出发，顺着箭头的方向走到任何其他点，然后再绕回来。
  • 缩点：在算法竞赛中，我们常把一个 SCC 看作一个“大点”，将有向图转化成一个有向无环图 (DAG)，从而利用拓扑排序或动态规划处理。
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
vector<int> adj[N];
// dfn[x] 时间戳 节点x第一次被访问的顺序
// low[x] 从x出发，可以访问到的最早的时间 
int dfn[N], low[N], timer;
int st[N], top;
bool inst[N];
int scc[N],siz[N],scc_cnt; // 每个点所属的 SCC 编号
void tarjan(int u) {
	// 入x时 入栈
    dfn[u] = low[u] = ++timer;
    st[++top] = u;
    inst[u] = true;
    for (int v : adj[u]) {
        if (!dfn[v]) { // 未访问过
            tarjan(v);
            low[u] = min(low[u], low[v]);// 回x时 更新low
        } else if (inst[v]) { // 在栈中，说明找到了环
            low[u] = min(low[u], dfn[v]);//更新low
        }
    }

    // 找到一个完整的 SCC
    if (low[u] == dfn[u]) {//如果x是SCC的根
        scc_cnt++;
        while (true) {
            int v = st[top--];
            inst[v] = false;
            scc[v] = scc_cnt;//SCC的编号
            ++siz[scc_cnt];//SCC大小
            if (u == v) break;
        }
    }
}

2. 弱连通分量 (WCC)

定义：
如果将有向图中的所有有向边都替换为无向边后，所得到的无向图是连通的，那么原有的有向图子图被称为弱连通的。

  • 直观理解：只要忽略箭头的方向，这些点是连在一起的。就像单行道组成的城市，虽然你可能无法从 A 经过单行道回到 B，但 A 和 B 之间确实有道路相连。
  • 特点：强连通一定是弱连通，但弱连通不一定是强连通。

处理：只需要把有向图当成无向图处理
1.遍历所有边，对于每条有向边 (u, v)，在并查集中执行合并
2.运行一次不考虑方向的 DFS

树问题

二叉树

把它想象成一棵“倒过来的树”

基础小知识

  • 根节点：最顶端的那个点，是所有数据的起点。
  • 边：连接各个点的线。
  • 叶子节点：最底端不再分叉的点
  • 节点的度：一个节点有多少个子节点（二叉树里最大就是 2）。
  • 叶子节点：度为 0 的节点。
  • 树的深度/高度：这棵树总共有多少层。
  • 空树：这也是一种合法的二叉树，里面一个节点都没有。

特殊的二叉树
1.满二叉树：除了最后一层的叶子节点外，每一层的每个节点都有两个子节点，并且最后一层全满。
2.完全二叉树：除了最后一层，其他各层的节点数都达到了最大值；最后一层的节点全部集中在该层最左边的若干位置上。

储存

1
2
3
4
5
6
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

遍历

前序遍历

根，左，右

1
2
3
4
5
6
void preOrder(TreeNode* root) {
    if (root == NULL) return; // 递归基：如果是空节点，直接返回
    cout << root->val << " "; // 根
    preOrder(root->left);     // 左
    preOrder(root->right);    // 右
}

中序遍历

左，根，右

1
2
3
4
5
6
void inOrder(TreeNode* root) {
    if (root == NULL) return;
    inOrder(root->left);      // 左
    cout << root->val << " "; // 根
    inOrder(root->right);     // 右
}

后序遍历

左，右，根

1
2
3
4
5
6
void postOrder(TreeNode* root) {
    if (root == NULL) return;
    postOrder(root->left);    // 左
    postOrder(root->right);   // 右
    cout << root->val << " "; // 根
}

层序遍历

使用queue（bfs）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void levelOrder(TreeNode* root) { 
	if (!root) return;
	queue<TreeNode*> q;
	q.push(root); 
	while (!q.empty())
	{
		TreeNode* curr = q.front();
		q.pop();
		cout << curr->val; 
		// 输出当前节点 
		if (curr->left)  q.push(curr->left);
		if (curr->right) q.push(curr->right);
	} 
	cout << endl;
}

树上差分

多次给每次给树上任意两点 u和 v之间的唯一最短路径上的所有点（或边）都加上一个值 k。
如果按常规思路，每次操作都沿着路径暴力往上爬，时间复杂度会很大，这时候我们就需要使用差分
不过在树上，我们需要借助一个关键辅助工具：最近公共祖先（LCA）

点差分

我们可以把 u→v的路径拆成两段：u→l和 v→l。

  • 当你在 diff[u] += k时，如果你后续进行子树求和（即从下往上累加），这个值会自动一路加到根节点。同理 diff[v] += k也会一路往上加。
  • 这样一来，l及以上的节点就被多加了两次（一次来自 u，一次来自 v）。
  • 所以我们需要在 diff[l] -= k（消掉多算的一次），并在 diff[f[l][0]] -= k。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 假设数组 d[] 为差分数组，初始全为0
// f[u][0] 代表 u 的父节点 (倍增法中的 parent)
void add_node(int x, int y, int k) {
    int l = lca(x, y);
    d[x] += k;
    d[y] += k;
    d[l] -= k;
    if (f[l][0] != 0) { // 防止数组越界，如果是根节点的父节点
        d[f[l][0]] -= k;
    }
}
//前缀和还原
void dfs_sum(int u, int p) {
    for (int v:adj[u]) {
        if (v == p) continue;
        dfs_sum(v, u);
        d[u] += d[v]; // 子节点的差分值累加给父节点
    }
    // 此时 d[u] 即为该点最终的权值
}

注意：
如果初始点权不为0 需要分开记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//val[]初始点权 d[]为差分数组
// 先跑一遍标准的差分还原 DFS
void dfs_sum(int u, int p) {
    for (int v :adj[u]) {
        if (v == p) continue;
        dfs_sum(v, u);
        d[u] += d[v]; // 此时 p[u] 变成了节点 u 的“总增加量”
    }
}
// ... 主函数中 ...
dfs_sum(1, 0);
// 输出时合并
for(int i = 1; i <= n; ++i) {
    cout << (val[i] + d[i]) << " "; 
}

边差分

  • 和刚才类似，diff[u] += k和 diff[v] += k会让 l以上的边多算两次。
  • 但因为这次我们操作的是边，在 l这个拐点，左右两边的边是不连通的（总不能把 l和它父亲的边也给加了）。
  • 所以我们需要在 l这里连减两次 k（一次抵消左边上来的，一次抵消右边上来的），从而把影响牢牢锁死在 u→l和 v→l这两段路径上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 假设数组 d[] 为差分数组
void add_edge(int x, int y, int k) {
    int l = lca(x, y);
    d[x] += k;
    d[y] += k;
    d[l] -= 2 * k; 
    // 注意：边差分不需要操作 f[l][0]
}
//前缀和还原
void dfs_sum(int u, int p) {
    for (int v:adj[u]) {
        if (v == p) continue;
        dfs_sum(v, u);
        d[u] += d[v]; 
    }
    // 此时 d[u] 代表 边(u, father) 最终的权值
}

树上前缀和

多次给询问树上的一系列权值和，我们就需要使用树上前缀和
树上前缀和也是一样，我们需要借助一个关键辅助工具：最近公共祖先（LCA）

点前缀和

定义 s[u]为 从根节点到 u的路径上所有点的权值之和。
那么路径 u→v的和为：
$$
Sum(u,v)=s[u]+s[v]−s[lca]−s[parent(lca)]
$$

1
2
3
4
5
6
7
8
9
int val[N];
ll s[N]; // 根节点到 u 的前缀和
void dfs_pre(int u, int p) {
    for (int v : adj[u]) {
        if (v == p) continue;
        s[v] = s[u] + val[v];
        dfs_pre(v, u);
    }
}

边前缀和

定义 s[u]为 从根节点到 u的路径上所有边的权值之和。
那么路径 u→v的和为：
$$
Sum(u,v)=s[u]+se[v]−2×s[lca]
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int eval[N];// eval[u] 存储 u 与父节点的边权
ll s[N]; // 根节点到 u 的路径边权和

void dfs_edge(int u, int p) {
    for (int v : adj[u]) {
        if (v == p) continue;
        // v 的父边权值是 edge_val[v]
        s[v] = s[u] + eval[v];
        dfs_edge(v, u);
    }
}
// 主函数
int main() {
    // 假设 1 是根
    s[1] = 0; 
    dfs_edge(1, 0);
}

最近公共祖先（LCA）

在之前提到的树上差分、路径前缀和中，LCA 都是必不可少的“中间变量”。
简单来说：LCA 就是两个节点在通往根节点的路径上，最先交汇的那个点。

1.倍增算法

时间复杂度：$O(VlogV)$
核心思想：
想象你要从节点 u走到根节点。如果一步一步走太慢，我们就尝试一次跳 1,2,4,8...步。

  • up[u][i]表示 节点 u的第 2^i级祖先。
  • 递推公式（倍增核心）：
    $$
    up[u][i]=up[up[u][i−1]][i−1]
    $$
    （意思是：u的第 2^i个祖先 = u的第 2^i-1个祖先的第 2^i−1个祖先）。
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
const int N=5e5+5;
vector<int> adj[N];
int n,m;
int dep[N],up[N][20];//2^20>5e5+5,如果N更大,那就不是20了
void dfs(int u,int p)
{
	dep[u]=dep[p]+1;
	//向上跳1 2 4 ...步的祖先节点
	up[u][0]=p;
	for(int i=1;i<=19;++i)
	{
		up[u][i]=up[up[u][i-1]][i-1];
	}
	for(int v:adj[u])
	{
		if(v!=p) dfs(v,u);
	}
}
int lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	//先跳到同一层
	for(int i=19;i>=0;--i)
	{
		if(dep[up[u][i]]>=dep[v])
		{
			u=up[u][i];
		}
	}
	if(u==v) return v;
	//然后跳到LCA的下一层
	for(int i=19;i>=0;--i)
	{
		if(up[u][i]!=up[v][i])
		{
			u=up[u][i],v=up[v][i];
		}
	}
	return up[u][0];
}

2.Tarijan

时间复杂度：$O(V+E)$
特点：极其高效，但必须把所有询问一次性读入，是一种离线算法
核心思想：
1.DFS 遍历：从根节点开始深度优先搜索。
2.vi数组标记：
- 未访问：还没搜到的节点。vi[u]=0
- 正在访问：已经在递归栈中，但还没回溯完成的节点。vi[u]=1
- 已访问：已经回溯完成，确定祖先关系的节点。 vi[u]=2
3.并查集维护：当一个节点 u回溯时，把它合并到它父节点的集合里。这意味着：对于已访问的节点，它的并查集根就是它在 DFS 树上的祖先。
关键逻辑：
当 DFS 到节点 u时，检查所有关于 u的询问 (u,v)：

  • 如果 v还没访问：不管。
  • 如果 v已经访问过：那么 LCA(u,v)就是 v所在的并查集的根。
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
const int N=5e5+5, M=1e5+5;
vector<int> adj[N];
int n,m;
vector<pair<int,int> > query[N];
int ans[M], fa[N];
int vis[N]; // 0=未访问, 1=正在访问, 2=已访问完毕

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

void tarjan(int u)
{
	//入u时,标记u为正在访问
	vis[u]=1;
	for(auto v:adj[u])
	{
		if(!vis[v]) 
		{
			tarjan(v);
			//回u时,v指向u
			f[v]=u;
		}
	}
	//离u时,枚举LCA
	for(auto q:query[u])
	{
		int v=q.first, i=q.second;
		// 必须是已经完全访问完毕(状态为2)的节点才能结算
		if(vis[v] == 2) ans[i]=find(v);
	}
	// 离开u时，标记u为已访问完毕
	vis[u]=2;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	int a,b;
	for(int i=1;i<n;++i)
	{
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for(int i=1;i<=m;++i)
	{
		cin>>a>>b;
		query[a].push_back({b,i});
		query[b].push_back({a,i});
	}
	for(int i=1;i<=n;++i) f[i]=i;
	
	tarjan(1); // 假设 1 为根节点
	
	for(int i=1;i<=m;++i) cout<<ans[i]<<"\n"; 
	return 0;
}

3.树链剖分

时间复杂度：$O(V + Q\log V)$
核心思想：将一棵树拆分成若干条互不相交的“链”。这样一来，树上的路径问题就被转化为了区间问题。
核心概念：

  • 重儿子：某个节点的子节点中，子树节点最多的那个子节点。
  • 轻儿子：除重儿子以外的其他子节点。
  • 重边：连接父节点与重儿子的边。
  • 轻边：连接父节点与轻儿子的边。
  • 重链：由多条重边首尾相连组成的链。每个节点都属于且仅属于一条重链（单独的叶子节点或轻儿子自己也可以看作一条长度为 0 的重链）。
  • 链头：重链上深度最小的那个节点。
    为了实现，我们需要两次dfs
    第一次 DFS：收集树的基础信息
    计算每个节点的深度（dep）、父亲（fa）、子树大小（siz），并找出每个节点的重儿子（son）。
    第二次 DFS：连线成链
    确定每个节点所在重链的链头（top）。优先走重儿子，再走轻儿子。
    原理：
  • 比较 u 和 v 所在的重链链头（top[u] 和 top[v]），谁的链头深度更深，谁就向上跳。
  • 假设 top[u] 更深，我们就让 u 直接跳到它当前链头的父亲节点：u = fa[top[u]]。
  • 重复这个过程，直到 u 和 v 进入同一条重链（即 top[u] == top[v]）。
  • 此时，u 和 v 已经在一条直链上了，深度较浅的那个节点就是它们的 LCA。
// 核心数组
vector<int> adj[N];
int sz[N],fa[N],dep[N],son[N];
int top[N],id[N],cnt;

// 1. 求重儿子、size、深度、父节点
void dfs1(int u,int p){
    fa[u]=p; dep[u]=dep[p]+1; sz[u]=1;son[u]=0;
    for(int v:adj[u]){
        if(v==f)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[v]]) son[u]=v;
    }
}

// 2. 剖分链，赋id
void dfs2(int u,int t){
    top[u]=t; id[u]=++cnt;
    if(son[u]) dfs2(son[u],t); // 重儿子同链
    for(int v:adj[u]){
        if(v!=fa[u]&&v!=son[u])
            dfs2(v,v); // 轻儿子新开链
    }
}
int get_lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
}
/*调用
dfs1(root, 0);
dfs2(root, root);
*/