cf1899G. Unusual Entertainment（启发式合并）

https://codeforces.com/contest/1899/problem/G
首先将将节点重新映射一下
然后就是个启发式合并板题

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const ll inf=1ll<<60;
const int N=2e5+5;
int n,x,y,q,z;
int head[N],to[N*2],nex[N*2],tot,p[N],len;
set<int> c[N];
struct node{
	int l,r,id;
};
vector<node> v[N];
bool ans[N];
void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x,int y){
	c[x].clear();
	c[x].insert(p[x]);
	for (int i=head[x];i;i=nex[i]) {
		int v=to[i];
		if (v==y) continue;
		dfs(v,x);
		
		if (c[x].size()<c[v].size()) c[x].swap(c[v]);
		for (auto j:c[v]) c[x].insert(j);
	}
	
	for (int i=0;i<(int)v[x].size();i++) {
		auto it=c[x].lower_bound(v[x][i].l);
		if (it==c[x].end()) {
			ans[v[x][i].id]=0;
		}
		else {
			if ((*it) <=v[x][i].r) ans[v[x][i].id]=1;
			else ans[v[x][i].id]=0;
		}
	}
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d %d",&n,&q);
	
		
		tot=0;
		fo(i,1,n) head[i]=0;
		fo(i,1,n-1) {
			scanf("%d %d",&x,&y);
			add(x,y); add(y,x);
		}
		
		fo(i,1,n) {
			v[i].clear();
			scanf("%d",&x);
			p[x]=i;
		}
		
		fo(i,1,q) {
			ans[i]=0;
			
			scanf("%d %d %d",&x,&y,&z);
			v[z].push_back((node){x,y,i});
		}
		
		dfs(1,0);
		
		fo(i,1,q) if (ans[i]) A;
		else B;

		puts("");
	}

	return 0;
}