题解
LCA的拓展题哦。
LCA计算\(dis(x,y)\)(边数),如果为奇则不存在距离相等的房间。如果为偶,设\(x,y\)路径中与2点距离相等的节点为\(a\)。假设现在整棵树的根节点为\(a\),\(x\)在\(a\)的子节点\(b\)的子树中,\(y\)在\(a\)的子节点\(c\)的子树中。易证,除\(b,c\)的子树以外,其他节点到\(x,y\)的距离都是相等的。现在考虑原本的图:设节点\(x\)的深度为\(d_x\),若\(d_x=d_y\),则\(b,c\)的子树与变换后的图相同;若\(d_x>d_y\),\(c\)的子树变为 变换后的图中\(c\)的子树加上不属于\(a\)的子树的部分,也就是所求的节点即为\(a\)的子树\(-b\)的子树,\(d_y>d_x\)同理。求出每个节点的子树大小,倍增找到\(b,c\)即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int fst[N],nxt[2*N],v[2*N],cnt;
int f[N][20],siz[N],d[N],logn;//siz[i]:i节点的子树大小
queue<int> q;
void add(int x,int y)
{
v[++cnt]=y;
nxt[cnt]=fst[x],fst[x]=cnt;
}
void bfs()
{
q.push(1); d[1]=1;
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=fst[x];i;i=nxt[i])
{
int y=v[i];
if(d[y]) continue;
d[y]=d[x]+1,f[y][0]=x;
for(int j=1;j<=logn;j++) f[y][j]=f[f[y][j-1]][j-1];
q.push(y);
}
}
}
void dfs(int x,int fa)//计算siz数组
{
siz[x]=1;
for(int i=fst[x];i;i=nxt[i])
{
int y=v[i];
if(y!=fa) {dfs(y,x); siz[x]+=siz[y];}
}
}
int lca(int x,int y)
{
if(d[x]<d[y]) swap(x,y);
for(int i=logn;i>=0;i--)
if(d[f[x][i]]>=d[y]) x=f[x][i];
if(x==y) return x;
for(int i=logn;i>=0;i--)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int find(int x,int y)//寻找x向上y级的祖先
{
for(int i=logn;i>=0;i--)
if((1<<i)<=y) x=f[x][i],y-=(1<<i);
return x;
}
int main()
{
int n,m,x,y;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
logn=log(n)/log(2)+1;
bfs(); dfs(1,0);
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&x,&y);
if(x==y) {printf("%d\n",n); continue;}
int tmp=lca(x,y),qwq=d[x]+d[y]-2*d[tmp],qaq,qoq;
//qwq:dis(x,y),qaq:上文中的b/c,qoq:上文中的c
if(qwq%2) {printf("0\n"); continue;}
if(d[x]==d[y])
{
qaq=find(x,qwq/2-1),qoq=find(y,qwq/2-1);
printf("%d\n",n-siz[qaq]-siz[qoq]); continue;
}
if(d[x]>d[y]) qaq=find(x,qwq/2-1);
else qaq=find(y,qwq/2-1);
printf("%d\n",siz[f[qaq][0]]-siz[qaq]);
}
return 0;
}