C++(clang++ 11.0.1) 解法, 执行用时: 635ms, 内存消耗: 51756K, 提交时间: 2023-07-09 21:38:37

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
ll dep[1010000],n,fa[1010000][22],lg[1010000];
ll sum[1010000],s1,s2;
int q;
vector<ll> p[1010000];
void dfs(ll now,ll bef)
{
	dep[now]=dep[bef]+1;
	fa[now][0]=bef;
	for(ll i=1;i<=20;i++)
	fa[now][i]=fa[fa[now][i-1]][i-1];
	for(ll i=0;i<p[now].size();i++)
	{
		ll tp=p[now][i];
		if(tp==bef) continue;
		dfs(tp,now);
		sum[now]+=sum[tp];
	}
	sum[now]++;
}
ll LCA(ll x,ll y)
{
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y])
	x=fa[x][lg[dep[x]-dep[y]]-1];
	if(x==y) return x;
	for(ll i=lg[dep[x]];i>=0;i--)
	if(fa[x][i]!=fa[y][i])
	x=fa[x][i],y=fa[y][i];
	
	return fa[x][0];
}
int main()
{
	cin>>n;
	for(ll i=1;i<n;i++)
	{
		ll x,y;
		cin>>x>>y;
		p[x].push_back(y);
		p[y].push_back(x);
	}
	for(ll i=1;i<=n;i++)
	lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	dfs(1,0);
	cin>>q;
	for(ll i=1;i<=q;i++)
	{
		ll x,y;
		cin>>x>>y;
		if(x==y) cout<<n<<endl;
		else if((abs(dep[x]-dep[y]))%2==1) cout<<0<<endl;
		else
		{
			ll t=LCA(x,y);
			if(dep[x]==dep[y])
			{
				ll s1=x,s2=y;
				for(ll i=20;i>=0;i--)
					if(dep[fa[s1][i]]>dep[t])
						s1=fa[s1][i];
				for(ll i=20;i>=0;i--)
					if(dep[fa[s2][i]]>dep[t])
						s2=fa[s2][i];
				ll ans=0;
				cout<<n-sum[s1]-sum[s2]<<endl;
			}
			else
			{
				if(dep[x]<dep[y]) swap(x,y);
				ll hr=(dep[x]-dep[y])/2;
				ll want=dep[t]+hr;
				ll s1=x;
				for(ll i=20;i>=0;i--)
					if(dep[fa[s1][i]]>want)
						s1=fa[s1][i];
				t=fa[s1][0];
				cout<<sum[t]-sum[s1]<<endl;
			}
		}
	}
}