题解：P7518 [省选联考 2021 A/B 卷] 宝石

#include<bits/stdc++.h>
using namespace std;
const int N= 2e5+100;
int n,m,c;
int ft[N],dep[N],siz[N],son[N],top[N],lf[N],cnt;
int P[N],pos[N],w[N],t[N];
int f[N*18],tot,k[N*18],to[N*18];
vector<int> a[N];
vector<int> st1[N],st2[N],ed1[N],ed2[N];
int ans[N];
struct st{int id,ad;};
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline void dfs(int x,int fa)
{
	ft[x]=fa,siz[x]=1;
	for(auto i:a[x])
	{
		if(i==fa)continue;
		dep[i]=dep[x]+1,dfs(i,x);
		siz[x]+=siz[i];
		if(siz[i]>siz[son[x]])son[x]=i;
	}
}
inline void dfs(int x)
{
	if(!son[x]){lf[++cnt]=x;return;}
	top[son[x]]=top[x];
	dfs(son[x]);
	for(auto i:a[x])if(i!=ft[x]&&i!=son[x])top[i]=i,dfs(i);
}
inline int lca(int x,int y)
{
	while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);x=ft[top[x]];}
	return dep[x]>dep[y]?y:x;
}
inline void work(int x,int y,int id)
{
	int lc=lca(x,y);
	ed2[y].push_back(id);
	while(top[y]!=top[lc])
	{
		ed2[ft[top[y]]].push_back(id);
		st2[top[y]].push_back(id);
		y=ft[top[y]];
	}
	st2[lc].push_back(id);
	ed1[lc].push_back(id);
	st1[x].push_back(id);
}
inline void uni(int x,int y)
{
	f[t[x]]=find(t[y]),t[x]=++tot,f[tot]=tot,k[t[x]]=x;
}
#define out(X) cerr<<X<<' '<<x<<' '<<i<<'\n';
inline void upp(int x)
{
	int ed=ft[top[x]];
	unordered_set<int> s;
	while(1)
	{
		for(auto i:st1[x])f[++tot]=t[ans[i]],to[i]=tot,s.insert(i);
		if(pos[w[x]])
			uni(pos[w[x]]-1,pos[w[x]]);
		for(auto i:ed1[x])
			ans[i]=k[find(to[i])],s.erase(i);
		x=ft[x];
		if(x==ed)
		{
			for(auto i:s)ans[i]=k[find(to[i])],st1[x].push_back(i);
			return;
		}
	}
}
inline void up(int x)
{
	x=top[x];
	unordered_set<int> s;
	while(1)
	{
		for(auto i:st2[x])f[++tot]=t[ans[i]],to[i]=tot,s.insert(i);
		if(pos[w[x]])
			uni(pos[w[x]]-1,pos[w[x]]);
		for(auto i:ed2[x])
			ans[i]=k[find(to[i])],s.erase(i);
		if(!son[x])return;
		x=son[x];
	}
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>c;
	for(int i=1;i<=c;i++)cin>>P[i],pos[P[i]]=i;
	for(int i=1;i<=n;i++)cin>>w[i];
	int x,y;
	for(int i=1;i<n;i++)cin>>x>>y,a[x].push_back(y),a[y].push_back(x);
	for(int i=0;i<=c;i++)t[i]=++tot,f[tot]=tot,k[tot]=i;
	dfs(1,0),top[1]=1,dfs(1);
	int qq;
	cin>>qq;
	for(int i=1;i<=qq;i++)cin>>x>>y,work(x,y,i);
	sort(lf+1,lf+cnt+1,[](int x,int y){return dep[top[x]]>dep[top[y]];});
	for(int i=1;i<=cnt;i++)upp(lf[i]);
	sort(lf+1,lf+cnt+1,[](int x,int y){return dep[top[x]]<dep[top[y]];});
	for(int i=1;i<=cnt;i++)up(lf[i]);
	for(int i=1;i<=qq;i++)
		cout<<ans[i]<<'\n';
}