题目描述
传送门
题目大意:每次询问到x,y距离相等的点有几个
题解
找到x,y路径的中点
除去中点连接的x,y所在的子树的size就是答案。
x,y有可能不在中点的子树中,两种情况分类讨论一下就可以了。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 200003
using namespace std;
int n,m,deep[N],f[N][20],mi[20],size[N],tot;
int point[N],v[N],next[N],num,num1;
void add(int x,int y)
{
tot++; next[tot]=point[x]; point[x]=tot; v[tot]=y;
tot++; next[tot]=point[y]; point[y]=tot; v[tot]=x;
}
void dfs(int x,int fa)
{
size[x]=1; deep[x]=deep[fa]+1;
for (int i=1;i<=19;i++) {
if (deep[x]-mi[i]<0) break;
f[x][i]=f[f[x][i-1]][i-1];
}
for (int i=point[x];i;i=next[i])
if (v[i]!=fa) {
f[v[i]][0]=x;
dfs(v[i],x);
size[x]+=size[v[i]];
}
}
int lca(int x,int y)
{
num=0;
if (deep[x]<deep[y]) swap(x,y);
int k=deep[x]-deep[y];
for(int i=0;i<=19;i++)
if (k>>i&1) x=f[x][i],num+=mi[i];
if (x==y) return y;
for (int i=19;i>=0;i--)
if (f[x][i]!=f[y][i]) {
x=f[x][i]; num+=mi[i];
y=f[y][i]; num+=mi[i];
}
num+=2;
return f[x][0];
}
int step(int x,int k)
{
num1=0;
for (int i=0;i<=19;i++)
if (k>>i&1) {
num1+=mi[i];
x=f[x][i];
}
return x;
}
int main()
{
freopen("date.in","r",stdin);
freopen("date.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<n;i++) {
int x,y; scanf("%d%d",&x,&y);
add(x,y);
}
mi[0]=1;
for (int i=1;i<=19;i++) mi[i]=mi[i-1]*2;
dfs(1,0);
scanf("%d",&m);
for (int i=1;i<=m;i++) {
int x,y; scanf("%d%d",&x,&y);
if (x==y) {
printf("%d\n",n);
continue;
}
int t=lca(x,y); int ans=0;
int dis=deep[x]-deep[t];
int dis1=deep[y]-deep[t];
if (dis==dis1) {
int now1=step(x,dis-1);
int now2=step(y,dis1-1);
ans=n-size[now1]-size[now2];
}
else {
if ((dis+dis1)%2==0) {
if (deep[x]<deep[y]) swap(x,y);
int now=step(x,(dis+dis1)/2);
int now2=step(x,(dis+dis1)/2-1);
ans=size[now]-size[now2];
}
else ans=0;
}
printf("%d\n",ans);
}
}