问题描述：

倍增法求LCA

#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <vector> #define CLOSE ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); #define isd(c) ('0' <= (c) && (c) <= '9') #define isa(c) ('a' <= (c) && (c) <= 'z') #define isA(c) ('A' <= (c) && (c) <= 'Z') #define mem(a, b) memset(a, b, sizeof a); #define N 500050 #define M 2000005 #define llm 9223372036854775807 #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define PI acos(-1) #define endl "\n" #define bug cout << endl << " .....here!...." << endl; using namespace std; const int maxk=20;//(int)(log(Maxn)/log(2)+1);//最大跳跃层数，即log2(MaxN) struct Edge { int to,next,w; }edge[M*2]; int head[N],cnt; void add(int a,int b) { edge[cnt].to=b; edge[cnt].next=head[a]; head[a]=cnt++; } int n,m,s; int deep[N],fa[N][maxk+1];//父亲及祖先节点,用于快速幂 void init() { cnt=0; memset(head,-1,sizeof head); memset(deep,0,sizeof deep); memset(fa,0,sizeof fa); } //dfs处理每个节点的父节点及深度 void dfs(int u) { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(deep[v]==0) { deep[v]=deep[u]+1; fa[v][0]=u;//f[now][0]记录当前节点父节点 dfs(v); } } return ; } //LCA预处理,处理fa数组 void prelca(int root) { deep[root]=1; dfs(root); for(int k=1;k<=maxk;k++) { for(int i=1;i<=n;i++)//f [ i ][ k ] 表示节点 i的第2^k个祖先节点编号 fa[i][k]=fa[fa[i][k-1]][k-1]; } return; } int LCA(int x,int y) { if(deep[x]<deep[y]) swap(x,y); int dd=deep[x]-deep[y]; for(int k=0;k<=maxk;k++) { if(1<<k & dd)//深度dd包含即2^k次方 x=fa[x][k];//将a上跳到其2^k祖先位置 } if(x==y) return x; for(int k=maxk;k>=0;k--) { if(fa[x][k]!=fa[y][k]) { x=fa[x][k]; y=fa[y][k]; } } return fa[x][0]; } int main() { CLOSE //cin>>n>>m>>s; scanf("%d%d%d",&n,&m,&s); init(); for(int i=1;i<n;i++) { int x,y; //cin>>x>>y; scanf("%d%d",&x,&y); add(x,y);add(y,x); } prelca(s); for(int i=1;i<=m;i++) { int x,y; //cin>>x>>y; scanf("%d%d",&x,&y); //cout<<LCA(x,y)<<endl; printf("%d\n",LCA(x,y)); } return 0; }

树上倍增维护路径最大最小值

void deal() { for(int i = 1 ; i <= 20 ; i ++) { for(int j = 1 ; j <= n ; j ++) { bz[j][i] = bz[bz[j][i-1]][i-1]; dp[j][i] = min(dp[j][i-1],dp[bz[j][i-1]][i-1]); } } } int LCA(int x, int y) { int ans = INF; if(dfn[x] < dfn[y]) swap(x,y); int t = deep[x] - deep[y]; for(int i = 0; (1<<i) <= t ; i ++) { if((1<<i)&t) { ans = min(ans,dp[x][i]); x = bz[x][i]; } } if(x == y) return ans; for(int i = 20 ; i >= 0 ; i --) { if(bz[x][i] ^ bz[y][i]) { ans = min(ans,dp[x][i]); ans = min(ans,dp[y][i]); x = bz[x][i]; y = bz[y][i]; } } ans = min(ans,dp[x][0]); ans = min(ans,dp[y][0]); return ans; }

树链剖分求LCA

int son[N], Size[N], top[N], fa[N], deep[N]; void dfs1(int u) { Size[u] = 1; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v != fa[u]) { fa[v] = u; deep[v] = deep[u] + 1; dfs1(v); Size[u] += Size[v]; if (Size[v] > Size[son[u]]) son[u] = v; } } } void dfs2(int u, int t) { top[u] = t; if (son[u]) dfs2(son[u], t); for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v != son[u] && v != fa[u]) dfs2(v, v); } } int lca(int x, int y) { while (top[x] != top[y]) { if (deep[top[x]] < deep[top[y]]) swap(x, y); x = fa[top[x]]; } return deep[x] > deep[y] ? y : x; }

Tarjan求LCA O(n+m)

int n,m,s; vector<pair<int,int> >ve[N]; int fa[N],vis[N],ans[N]; void init() { cnt=0; memset(head,-1,sizeof head); for(int i=1;i<=n;i++) fa[i]=i; } int Find(int x) { if(x==fa[x]) return x; return fa[x]=Find(fa[x]); } void Union(int x,int y) { x=Find(x),y=Find(y); if(x!=y) fa[x]=y; } void tarjan(int u,int father) { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(father==v) continue; tarjan(v,u); Union(v,u); } vis[u]=1; for(int i=0;i<ve[u].size();i++) if(vis[ve[u][i].first]) ans[ve[u][i].second]=Find(ve[u][i].first); } int main() { cin>>n>>m>>s; init(); for(int i=1;i<n;i++) { int x,y; cin>>x>>y; add(x,y,1); add(y,x,1); } for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; ve[x].push_back({y,i}); ve[y].push_back({x,i}); } tarjan(s,-1); for(int i=1;i<=m;i++) cout<<ans[i]<<endl; return 0; }

欧拉序ST表求LCA

int dep[N]; //记录深度用于ST表求LCA int f[N << 1][25]; //用于ST表求LCA int euler[N << 1] , pos[N], lg[N << 1], tot; //用于ST表求LCA void dfs1(int u , int fa, int deep) { dep[u] = deep; for (int i = head[u] ; i != -1 ; i = edge[i].next) { int v = edge[i].t; ll w = edge[i].w; if(v != fa) dfs1 (v , u, deep + 1); } } //处理出欧拉序 void dfs2(int u , int fa) { euler[++ tot] = u ; pos[u] = tot ; for(int i = head[u] ; i != -1 ; i = edge[i].next) { int v = edge[i].t ; if(v == fa) continue ; dfs2(v , u) ; euler[++ tot] = u ; } } //预处理log数组以及关于LCA的ST表 void Init_LCA() { lg[1] = 0; for (int i = 2; i <= tot; i++) lg[i] = lg[i >> 1] + 1; for (int i = 1 ; i <= tot ; i ++) f[i][0] = euler[i] ; for (int j = 1 ; j <= 20 ; j ++) { for (int i = 1; i <= tot - (1 << j); i++) { if (dep[f[i][j - 1]] < dep[f[i + (1 << (j - 1))][j - 1]]) f[i][j] = f[i][j - 1]; else f[i][j] = f[i + (1 << (j - 1))][j - 1]; } } } //求LCA int LCA(int x , int y) { int ans ; if(pos[x] > pos[y]) swap(x , y) ; int l1 = pos[x] , l2 = pos[y] ; //int len = log2(l2 - l1 + 1) ; int len = lg[l2 - l1 + 1] ; if(dep[f[l1][len]] < dep[f[l2 - (1 << len) + 1][len]]) ans = f[l1][len] ; else ans = f[l2 - (1 << len) + 1][len] ; return ans ; }

树上差分

image-20251218152227059686×830 19.7 KB

不能让lca加，uv减，因为这样的话x也会跟着变化。

u的父节点是唯一的，但是lca的子节点不唯一。

点差分

[P11967 [GESP202503 八级] 割裂](P11967 [GESP202503 八级] 割裂)

用于路径修改，并且在所有修改后只查询一次的问题

diff[u]+=x,diff[v]+=x,diff[lca]-=w,diff[p]-=w; //（ p为lca的父亲）

边差分

CF191C Fools and Roads

diff[u] += x,diff[v] += x,diff[lca] -= 2*w; //（将边权往深度大的节点塞），边的权值记录到子节点上 网友解答：

---

--【壹】--：

倍增法求LCA

#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <vector> #define CLOSE ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); #define isd(c) ('0' <= (c) && (c) <= '9') #define isa(c) ('a' <= (c) && (c) <= 'z') #define isA(c) ('A' <= (c) && (c) <= 'Z') #define mem(a, b) memset(a, b, sizeof a); #define N 500050 #define M 2000005 #define llm 9223372036854775807 #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define PI acos(-1) #define endl "\n" #define bug cout << endl << " .....here!...." << endl; using namespace std; const int maxk=20;//(int)(log(Maxn)/log(2)+1);//最大跳跃层数，即log2(MaxN) struct Edge { int to,next,w; }edge[M*2]; int head[N],cnt; void add(int a,int b) { edge[cnt].to=b; edge[cnt].next=head[a]; head[a]=cnt++; } int n,m,s; int deep[N],fa[N][maxk+1];//父亲及祖先节点,用于快速幂 void init() { cnt=0; memset(head,-1,sizeof head); memset(deep,0,sizeof deep); memset(fa,0,sizeof fa); } //dfs处理每个节点的父节点及深度 void dfs(int u) { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(deep[v]==0) { deep[v]=deep[u]+1; fa[v][0]=u;//f[now][0]记录当前节点父节点 dfs(v); } } return ; } //LCA预处理,处理fa数组 void prelca(int root) { deep[root]=1; dfs(root); for(int k=1;k<=maxk;k++) { for(int i=1;i<=n;i++)//f [ i ][ k ] 表示节点 i的第2^k个祖先节点编号 fa[i][k]=fa[fa[i][k-1]][k-1]; } return; } int LCA(int x,int y) { if(deep[x]<deep[y]) swap(x,y); int dd=deep[x]-deep[y]; for(int k=0;k<=maxk;k++) { if(1<<k & dd)//深度dd包含即2^k次方 x=fa[x][k];//将a上跳到其2^k祖先位置 } if(x==y) return x; for(int k=maxk;k>=0;k--) { if(fa[x][k]!=fa[y][k]) { x=fa[x][k]; y=fa[y][k]; } } return fa[x][0]; } int main() { CLOSE //cin>>n>>m>>s; scanf("%d%d%d",&n,&m,&s); init(); for(int i=1;i<n;i++) { int x,y; //cin>>x>>y; scanf("%d%d",&x,&y); add(x,y);add(y,x); } prelca(s); for(int i=1;i<=m;i++) { int x,y; //cin>>x>>y; scanf("%d%d",&x,&y); //cout<<LCA(x,y)<<endl; printf("%d\n",LCA(x,y)); } return 0; }

树上倍增维护路径最大最小值

void deal() { for(int i = 1 ; i <= 20 ; i ++) { for(int j = 1 ; j <= n ; j ++) { bz[j][i] = bz[bz[j][i-1]][i-1]; dp[j][i] = min(dp[j][i-1],dp[bz[j][i-1]][i-1]); } } } int LCA(int x, int y) { int ans = INF; if(dfn[x] < dfn[y]) swap(x,y); int t = deep[x] - deep[y]; for(int i = 0; (1<<i) <= t ; i ++) { if((1<<i)&t) { ans = min(ans,dp[x][i]); x = bz[x][i]; } } if(x == y) return ans; for(int i = 20 ; i >= 0 ; i --) { if(bz[x][i] ^ bz[y][i]) { ans = min(ans,dp[x][i]); ans = min(ans,dp[y][i]); x = bz[x][i]; y = bz[y][i]; } } ans = min(ans,dp[x][0]); ans = min(ans,dp[y][0]); return ans; }

树链剖分求LCA

int son[N], Size[N], top[N], fa[N], deep[N]; void dfs1(int u) { Size[u] = 1; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v != fa[u]) { fa[v] = u; deep[v] = deep[u] + 1; dfs1(v); Size[u] += Size[v]; if (Size[v] > Size[son[u]]) son[u] = v; } } } void dfs2(int u, int t) { top[u] = t; if (son[u]) dfs2(son[u], t); for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v != son[u] && v != fa[u]) dfs2(v, v); } } int lca(int x, int y) { while (top[x] != top[y]) { if (deep[top[x]] < deep[top[y]]) swap(x, y); x = fa[top[x]]; } return deep[x] > deep[y] ? y : x; }

Tarjan求LCA O(n+m)

int n,m,s; vector<pair<int,int> >ve[N]; int fa[N],vis[N],ans[N]; void init() { cnt=0; memset(head,-1,sizeof head); for(int i=1;i<=n;i++) fa[i]=i; } int Find(int x) { if(x==fa[x]) return x; return fa[x]=Find(fa[x]); } void Union(int x,int y) { x=Find(x),y=Find(y); if(x!=y) fa[x]=y; } void tarjan(int u,int father) { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(father==v) continue; tarjan(v,u); Union(v,u); } vis[u]=1; for(int i=0;i<ve[u].size();i++) if(vis[ve[u][i].first]) ans[ve[u][i].second]=Find(ve[u][i].first); } int main() { cin>>n>>m>>s; init(); for(int i=1;i<n;i++) { int x,y; cin>>x>>y; add(x,y,1); add(y,x,1); } for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; ve[x].push_back({y,i}); ve[y].push_back({x,i}); } tarjan(s,-1); for(int i=1;i<=m;i++) cout<<ans[i]<<endl; return 0; }

欧拉序ST表求LCA

int dep[N]; //记录深度用于ST表求LCA int f[N << 1][25]; //用于ST表求LCA int euler[N << 1] , pos[N], lg[N << 1], tot; //用于ST表求LCA void dfs1(int u , int fa, int deep) { dep[u] = deep; for (int i = head[u] ; i != -1 ; i = edge[i].next) { int v = edge[i].t; ll w = edge[i].w; if(v != fa) dfs1 (v , u, deep + 1); } } //处理出欧拉序 void dfs2(int u , int fa) { euler[++ tot] = u ; pos[u] = tot ; for(int i = head[u] ; i != -1 ; i = edge[i].next) { int v = edge[i].t ; if(v == fa) continue ; dfs2(v , u) ; euler[++ tot] = u ; } } //预处理log数组以及关于LCA的ST表 void Init_LCA() { lg[1] = 0; for (int i = 2; i <= tot; i++) lg[i] = lg[i >> 1] + 1; for (int i = 1 ; i <= tot ; i ++) f[i][0] = euler[i] ; for (int j = 1 ; j <= 20 ; j ++) { for (int i = 1; i <= tot - (1 << j); i++) { if (dep[f[i][j - 1]] < dep[f[i + (1 << (j - 1))][j - 1]]) f[i][j] = f[i][j - 1]; else f[i][j] = f[i + (1 << (j - 1))][j - 1]; } } } //求LCA int LCA(int x , int y) { int ans ; if(pos[x] > pos[y]) swap(x , y) ; int l1 = pos[x] , l2 = pos[y] ; //int len = log2(l2 - l1 + 1) ; int len = lg[l2 - l1 + 1] ; if(dep[f[l1][len]] < dep[f[l2 - (1 << len) + 1][len]]) ans = f[l1][len] ; else ans = f[l2 - (1 << len) + 1][len] ; return ans ; }

树上差分

image-20251218152227059686×830 19.7 KB

不能让lca加，uv减，因为这样的话x也会跟着变化。

u的父节点是唯一的，但是lca的子节点不唯一。

点差分

[P11967 [GESP202503 八级] 割裂](P11967 [GESP202503 八级] 割裂)

用于路径修改，并且在所有修改后只查询一次的问题

diff[u]+=x,diff[v]+=x,diff[lca]-=w,diff[p]-=w; //（ p为lca的父亲）

边差分

CF191C Fools and Roads

diff[u] += x,diff[v] += x,diff[lca] -= 2*w; //（将边权往深度大的节点塞），边的权值记录到子节点上