题解
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); 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
"); continue;}
if(d[x]==d[y])
{
qaq=find(x,qwq/2-1),qoq=find(y,qwq/2-1);
printf("%d
",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
",siz[f[qaq][0]]-siz[qaq]);
}
return 0;
}