[模板]长链剖分形式LCA

# 长链剖分形式LCA模板 ```cpp #include <bits/stdc++.h> using namespace std; int n,m,s; const int maxn = 500010; struct edge{ int v,nxt; }E[maxn*2]; int p[maxn],eid; void init(){ memset(p,-1,sizeof p); eid = 0; } void insert(int u,int v){ E[eid].v = v; E[eid].nxt = p[u]; p[u] = eid++; } void insert2(int u,int v){ insert(u,v); insert(v,u); } int fa[maxn],dep[maxn],sz[maxn],hson[maxn]; void dfs1(int u){ sz[u] = 1; dep[u] = dep[fa[u]] + 1; for(int i=p[u];~i;i=E[i].nxt){ int v = E[i].v; if(v != fa[u]){ fa[v] = u; dfs1(v); sz[u] += sz[v]; if(sz[v] > sz[hson[u]]){ hson[u] = v; } } } } int top[maxn]; void dfs2(int u,int tp){ top[u] = tp; if(hson[u]){ //有重儿子就走重儿子 dfs2(hson[u],tp); } for(int i=p[u];~i;i=E[i].nxt){ int v = E[i].v; if(v != fa[u] && v != hson[u]){ dfs2(v,v); } } } int lca(int x,int y){ while(top[x] != top[y]){ if(dep[top[x]] > dep[top[y]]) swap(x,y); y = fa[top[y]]; } return dep[x] < dep[y] ? x : y; } int main(){ init(); scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n-1;i++){ int u,v; scanf("%d%d",&u,&v); insert2(u,v); } dfs1(s); dfs2(s,s); for(int i=1;i<=m;i++){ int xx,yy; scanf("%d%d",&xx,&yy); printf("%d\n",lca(xx,yy)); } return 0; } ```