树剖真的快

LCA（最近公共祖先）模板，对数复杂度查询

纯他妈左脑缺失指令集，右脑确实运行库，大脑丢包，小脑弹窗.

广搜+ST表

#include<bits/stdc++.h> using namespace std; const int maxn=5e5+5,LOG=20; vector<int>e[maxn]; int dep[maxn];//dep[u]表示节点u的深度 int f[maxn][LOG];//fa[u][k]表示节点u的2^k级祖先 int n,m,s; //注意：如果u节点没有2^k级节点，则将其设成0 //DFS预处理每个结点的深度和倍增表 void dfs(int now,int last){ //动态规划预处理2^k级祖先(k从1到LOG-1) for(int k=1;k<LOG;k++){ //u的2k祖先=(u的2{k-1}祖先)的2^{k-1}祖先 f[now][k]=f[f[now][k-1]][k-1]; } //递归处理子节点 for(int v : e[now]){ if (vlast) continue; dep[v]=dep[now]+1;//深度=父节点深度+1 f[v][0]=now;//u的2^0级祖先即直接父节点 dfs(v,now); } } //查询节点u和v的最近公共祖先(LCA) int LCA(int u,int v){ //第一步：确保u是较深节点 if(dep[u]<dep[v]) swap(u,v); //第二步：深度对齐(u上移至与v共同深度) for(int k=LOG-1;k>=0;k--){ //若u能上移2^k层且不越过v的深度，则上移 if(dep[f[u][k]]>=dep[v]) u=f[u][k]; } if(uv) return u;//此时v就是LCA //第三步：同步上移找LCA for(int k=LOG-1;k>=0;k--){ //若u和v的2^k祖先不同，则同步上移 if(f[u][k]!=f[v][k]) u=f[u][k],v=f[v][k]; } return f[u][0];//最终u和v的父节点即为LCA } int main(){ cin>>n>>m>>s; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; e[u].push_back(v); e[v].push_back(u); } dep[s]=1; dfs(s,0);//从根节点开始DFS while(m--){ int u,v; cin>>u,v; cout<<LCA(u,v)<<endl; } }

#include <bits/stdc++.h> using namespace std; int n,m,s,x,y,a,b,fa[500100][20],dep[500100]; vector<int> e[500100]; void dfs(int now,int last){ dep[now]=dep[last]+1; fa[now][0]=last; for(auto t:e[now]){ if(t!=last){ dfs(t,now); } } } int lca(int a,int b){ if(dep[a]<dep[b])swap(a,b); if(ab)return a; if(as)return a; if(bs)return b; for(int i=19;i>=0;i--){ if(dep[fa[a][i]]>=dep[b])a=fa[a][i]; } if(ab)return a; for(int i=19;i>=0;i--){ if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i]; } return fa[a][0]; } int main(){ cin >> n >> m >> s; for(int i=1;i<n;i++){ cin >> x >> y; e[x].push_back(y); e[y].push_back(x); } dfs(s,0); for(int j=1;j<=19;j++){ for(int i=1;i<=n;i++){ fa[i][j]=fa[fa[i][j-1]][j-1]; } } for(int i=1;i<=m;i++){ cin >> a >> b; cout << lca(a,b) << endl; } return 0; }