（2022牛客多校三）A-Ancestor（LCA）

题目：

样例1输入： 

5 3
5 4 3
6 6 3 4 6
1 2 2 4
7 4 5 7 7
1 1 3 2

样例1输出：

1

样例2输入：

10 3
10 9 8
8 9 9 2 7 9 0 0 7 4
1 1 2 4 3 4 2 4 7
7 7 2 3 4 5 6 1 5 3
1 1 3 1 2 4 7 3 5

样例2输出：

2

题意：给出两棵编号为1~n的树A，B，A树和B树上每个节点均有一个权值，给出k个关键点编号x1,x2……，xk，问有多少种方案使得去掉一个关键点使得剩余关键点在树A上的LCA的权值大于树B上LCA的权值。

注意：此处的去掉一个关键点只是不考虑它而已，并不是真正意义上的不能经过这个点什么的，比如去掉第1个特殊点，意思就是在原树上求解x2……，xk的LCA。

分析：LCA就是树上公共祖先，不会LCA的小伙伴可以看下这里：最近公共祖先（LCA）（树上倍增）_AC__dream的博客-CSDN博客_最近公共祖先

这道题我们可以预处理出来关键点序列在A树和B树上的前缀LCA和后缀LCA

代码中变量：

lcaprea[i]表示a中前i个点中的特殊点的LCA值，lcasufa[i]表示a中点i~n中的特殊点的LCA值

lcapreb[i]表示b中前i个点中的特殊点的LCA值，lcasufb[i]表示b中点i~n中的特殊点的LCA值

比如求解去掉第i个特殊点剩余的特殊点在A树上和B上的LCA，那么就是求解求解x1,x2……，xi-1，xi+1,……,xk在A树上和B树上的LCA，由于我们已经预处理出来了LCA前后缀，那么x1,x2……，xi-1，xi+1,……,xk在A树上的LCA就是lcaprea[i-1]和lcasufa[i+1]在A树上的最近公共祖先，x1,x2……，xi-1，xi+1,……,xk在B树上的LCA就是lcapreb[i-1]和lcasufb[i+1]在B树上的最近公共祖先。那么我们就可以直接枚举所有的特殊点进行判断即可。

下面是代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e6+10;
bool vis[N];
int wa[N],wb[N],fa[N][21],fb[N][21];
int h1[N],e1[N*10],ne1[N*10],idx;
int h2[N],e2[N*10],ne2[N*10],d1[N],d2[N];
int lcaprea[N],lcasufa[N];//lcaprea[i]表示a中前i个点中的特殊点的lca值，lcasufa[i]表示a中点i~n中的特殊点的lca值
int lcapreb[N],lcasufb[N];//lcapreb[i]表示b中前i个点中的特殊点的lca值，lcasufb[i]表示b中点i~n中的特殊点的lca值
void add(int x,int y,int p)
{
	if(p==1)
	{
		e1[idx]=y;
		ne1[idx]=h1[x];
		h1[x]=idx++;
	}
	else
	{
		e2[idx]=y;
		ne2[idx]=h2[x];
		h2[x]=idx++;
	}
}
void dfs1(int x,int father)
{
	d1[x]=d1[father]+1;//计算深度 
	fa[x][0]=father;
	for(int i=1;i<=20;i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=h1[x];i!=-1;i=ne1[i])
	{
		int j=e1[i];
		if(j==father) continue;
		dfs1(j,x);
	}
}
void dfs2(int x,int father)
{
	d2[x]=d2[father]+1;//计算深度 
	fb[x][0]=father;
	for(int i=1;i<=20;i++)
		fb[x][i]=fb[fb[x][i-1]][i-1];
	for(int i=h2[x];i!=-1;i=ne2[i])
	{
		int j=e2[i];
		if(j==father) continue;
		dfs2(j,x);
	}
}
int lca(int x,int y,int op)
{
	if(x==0) return y;
	if(y==0) return x;
	if(op==1)
	{
		if(d1[x]<d1[y]) swap(x,y);
		for(int i=20;i>=0;i--)//需要先将x和y移至同一高度 
			if(d1[fa[x][i]]>=d1[y])
				x=fa[x][i];
		if(x==y)	return x;
		for(int i=20;i>=0;i--)
			if(fa[x][i]!=fa[y][i])
			{
				x=fa[x][i];
				y=fa[y][i];
			}
		return fa[x][0];
	}
	else
	{
		if(d2[x]<d2[y]) swap(x,y);
		for(int i=20;i>=0;i--)//需要先将x和y移至同一高度 
			if(d2[fb[x][i]]>=d2[y]) 
				x=fb[x][i];
		if(x==y)	return x;
		for(int i=20;i>=0;i--)
			if(fb[x][i]!=fb[y][i])
			{
				x=fb[x][i];
				y=fb[y][i];
			}
		return fb[x][0];
	}
}
int main()
{
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		int t;
		scanf("%d",&t);
		vis[t]=true;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&wa[i]);
		h1[i]=h2[i]=-1;
	}
	for(int i=2;i<=n;i++)
	{
		int t;
		scanf("%d",&t);
		add(t,i,1);
	}
	for(int i=1;i<=n;i++)
		scanf("%d",&wb[i]);
	for(int i=2;i<=n;i++)
	{
		int t;
		scanf("%d",&t);
		add(t,i,2);
	}
	dfs1(1,-1);
	dfs2(1,-1);
	int lca1=-1,lca2=-1;
	for(int i=1;i<=n;i++)
	{
		if(vis[i])
		{
			if(lca1==-1) lca1=lca2=i;
			else
			{
				lca1=lca(lca1,i,1);
				lca2=lca(lca2,i,2);
			}
		}
	}
	int t=0;
	for(int i=1;i<=n;i++)
	{
		if(vis[i])
		{
			if(!t) t=i;
			else t=lca(t,i,1);
		}
		lcaprea[i]=t;
	}
	t=0;
	for(int i=n;i>=1;i--)
	{
		if(vis[i])
		{
			if(!t) t=i;
			else t=lca(t,i,1);
		}
		lcasufa[i]=t;
	}
	t=0;
	for(int i=1;i<=n;i++)
	{
		if(vis[i])
		{
			if(!t) t=i;
			else t=lca(t,i,2);
		}
		lcapreb[i]=t;
	}
	t=0;
	for(int i=n;i>=1;i--)
	{
		if(vis[i])
		{
			if(!t) t=i;
			else t=lca(t,i,2);
		}
		lcasufb[i]=t;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	if(vis[i])
	{
		int ta=lca(lcaprea[i-1],lcasufa[i+1],1);
		int tb=lca(lcapreb[i-1],lcasufb[i+1],2);
		if(wa[ta]>wb[tb]) ans++;
	}
	printf("%d",ans);
	return 0;
}