萌新求助,LCA WA了
查看原帖
萌新求助,LCA WA了
92682
Eric_cai楼主2021/2/2 15:17
#include<iostream>
#include<cstdio>
#define maxn 100005
using namespace std;
struct Eric_cai
{
	int to,next;
};
Eric_cai EC[maxn<<1];
int head[maxn],cnt;
void add(int u,int v)
{
	EC[++cnt].to=v;
	EC[cnt].next=head[u];
	head[u]=cnt;
}
int n,q;
int fa[maxn][32],dep[maxn],sz[maxn];
void dfs(int now,int f)
{
	sz[now]=1;
	fa[now][0]=f;
	dep[now]=dep[f]+1;
	for(int i=head[now];i!=0;i=EC[i].next)
	{
		if(EC[i].to==f) continue;
		dfs(EC[i].to,now);
		sz[now]+=sz[EC[i].to];
	}
}
void ST()
{
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i<=n;i++)
			fa[i][j]=fa[fa[i][j-1]][j-1];
}
int climb(int u,int depth)
{
	for(int i=20;i>=0;i--)
		if(fa[u][i]>=depth) u=fa[u][i];
	return u;
}
int get_lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	u=climb(u,dep[v]);
	if(u==v) return u;
	for(int i=20;i>=0;i--)
	{
		if(fa[u][i]!=fa[v][i])
		{
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}
int dist(int u,int v)
{
	int lca=get_lca(u,v);
	return dep[u]+dep[v]-2*dep[lca];
}
int query(int u,int v)
{
	if(u==v) return n;
	if(dist(u,v)%2==1) return 0;
	int lca=get_lca(u,v);
	if(dist(u,lca)==dist(v,lca)) 
	    return n-sz[climb(u,dep[lca]+1)]-sz[climb(v,dep[lca]+1)];
	else
	{
		if(dep[u]<dep[v]) swap(u,v);
		int x=climb(u,dep[u]-dist(u,v)/2);
		int y=climb(u,dep[u]-dist(u,v)/2+1);
		return sz[x]-sz[y];
	}
}
int main()
{
	int u,v;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
	ST();
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&u,&v);
		printf("%d\n",query(u,v));
	}
	return 0;
}
2021/2/2 15:17
加载中...