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;
}