树链剖分
2026-04-18 10:14:55
发布于：广东
8阅读
0回复
0点赞
板子
#include<iostream>
#include<vector>
using namespace std;
const int N = 1e5+5;
int n,q;
int fa[N];
int sz[N];
int son[N];
int top[N];
int deep[N];
vector<int> g[N];
void dfs1(int u,int f)
{
sz[u] = 1;
fa[u] = f;
deep[u] = deep[f]+1;
for(auto v:g[u])
{
if(v==f) continue;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v]) son[u] = v;
}
}
void dfs2(int u,int st)
{
top[u] = st;
if(son[u]==0) return ;
dfs2(son[u],st);
for(auto v:g[u])
{
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
int LCA(int u,int v)
{
while(top[u]!=top[v])
{
if(deep[top[u]]<deep[top[v]]) swap(u,v);
u = fa[top[u]];
}
if(deep[u]<deep[v]) return u;
else return v;
}
int main()
{
cin>>n;
for(int i=1;i<=n-1;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0);
dfs2(1,1);
cin>>q;
while(q--)
{
int u,v;
cin>>u>>v;
int lca = LCA(u,v);
cout<<deep[u]+deep[v]-2*deep[lca]<<'\n';
}
return 0;
}
有帮助，赞一个