2021.08.10【NOIP提高B組】模拟 祖孫詢問

思路：

LCA闆題

c o d e code code

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int n, tot, m;
int f[100100][25], head[100100], dep[100100];
struct node
{
	int to, next;
}b[1000100];

void add(int x, int y)
{
	b[++tot]=(node){y, head[x]};
	head[x]=tot;
}

void dfs(int x, int fa)
{
	f[x][0]=fa;
	dep[x]=dep[fa]+1;
	for(int i=head[x]; i; i=b[i].next)
	{
		int y=b[i].to;
		if(y==fa)
			continue;
		dfs(y, x);
	}
}

int lca(int x, int y)
{
	if(dep[y]>dep[x])
		swap(x, y);
	int k=dep[x]-dep[y], j=20, t=1<<20;
	while(k!=0)
	{
		if(k>=t)
			k-=t, x=f[x][j];
		j--, t=1<<j;
	}
	if(x==y)
		return x;
	for(int j=20; j>=0; j--)
		if(f[x][j]!=f[y][j])
			x=f[x][j], y=f[y][j];
	if(f[x][0]==f[y][0])
		return f[x][0];
	else
		return -1;
}

int main()
{
	scanf("%d", &n);
	int c=0, maxn=n;
	for(int i=1; i<=n; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		if(y==-1)
			c=x;
		else
			add(x, y), add(y, x);
		maxn=max(maxn, max(x, y));
	}
	n=maxn;
	dfs(c, 0);
	for(int j=1; j<=20; j++) 
		for(int i=1; i<=n; i++)
			f[i][j]=f[f[i][j-1]][j-1];
	scanf("%d", &m);
	while(m--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		int k1=lca(x, y);
		if(k1==x)
			printf("%d\n", 1);
		else if(k1==y)
			printf("%d\n", 2);
		else printf("%d\n", 0);
	}
	return 0;
}