RT,求帮忙看看下面这个LCA板子有没有问题。感激不尽!
void dfs(int u,int fa)
{
for(int i=1;i<=19;i++) f[i][u]=f[i-1][f[i-1][u]];
for(int i=head[u];~i;i=a[i].nxt)
{
int v=a[i].to;
if(v==fa) continue;
dis[v]=dis[u]+a[i].w;
dep[v]=dep[u]+1;
f[0][v]=u;
dfs(v,u);
}
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;i--)
if(dep[f[i][x]]<=dep[y]&&f[i][x]) x=f[i][x];
if(x==y) return x;
for(int i=19;i>=0;i--)
if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
return f[0][x];
}
inline ll Dis(int x,int y){return dis[x]+dis[y]-(dis[lca(x,y)]<<1);}