(2022 Niuke multi school III) a-ancestor (LCA)

subject ：

Examples 1 Input ： 

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

Examples 1 Output ：

1

Examples 2 Input ：

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

Examples 2 Output ：

2

The question ： Give two trees numbered 1~n The tree of A,B,A Trees and B Each node in the tree has a weight , give k Key point numbers x1,x2……,xk, Ask how many ways to remove a key point and make the remaining key points in the tree A Upper LCA The weight of is greater than that of the tree B On LCA A weight .

Be careful ： One key point is removed here, but it is not considered , It's not true that you can't go through this point , For example, remove No 1 Special points , It means solving on the original tree x2……,xk Of LCA.

analysis ：LCA Is the common ancestor on the tree , Can't LCA My little friend can have a look here ： Recent public ancestor （LCA）（ On the tree ）_AC__dream The blog of -CSDN Blog _ Recent public ancestor

We can The sequence of key points after preprocessing is A Trees and B Prefix on tree LCA And suffixes LCA

Variables in code ：

lcaprea[i] Express a Middle front i Special points among the points LCA value ,lcasufa[i] Express a Midpoint i~n Special points in LCA value

lcapreb[i] Express b Middle front i Special points among the points LCA value ,lcasufb[i] Express b Midpoint i~n Special points in LCA value

For example, get rid of number i The remaining special points are A Tree and B Upper LCA, Then it is to solve x1,x2……,xi-1,xi+1,……,xk stay A Tree and B On the tree LCA, Because we have preprocessed it LCA Prefix , that x1,x2……,xi-1,xi+1,……,xk stay A On the tree LCA Namely lcaprea[i-1] and lcasufa[i+1] stay A The nearest common ancestor on the tree ,x1,x2……,xi-1,xi+1,……,xk stay B On the tree LCA Namely lcapreb[i-1] and lcasufb[i+1] stay B The nearest common ancestor on the tree . Then we can directly enumerate all the special points for judgment .

Here is the code ：

#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] Express a Middle front i Special points among the points lca value ,lcasufa[i] Express a Midpoint i~n Special points in lca value 
int lcapreb[N],lcasufb[N];//lcapreb[i] Express b Middle front i Special points among the points lca value ,lcasufb[i] Express b Midpoint i~n Special points in lca value 
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;// Calculate the depth  
	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;// Calculate the depth  
	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--)// You need to x and y Move to the same height  
			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--)// You need to x and y Move to the same height  
			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;
}