Unusual Entertainment
题解
真的不要太典，，，
考虑点 \(u\) 是 \(v\) 的后代等价于 \(u\) 在子树 \(v\) 中，dfs 序直接走起，变成判断是否存在 \(i\) 使得：
\[in_x\le in_{p_i}\le out_x,l\le i\le r \]二维数点，启动！
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int tt,n,q,p[100005],ans[100005];
int h[100005],cnt;
struct QWQ{int v,nxt;} e[100005*2];
void add(int u,int v) {e[++cnt]={v,h[u]},h[u]=cnt;}
int in[100005],out[100005],tot;
void dfs(int u,int p) {
in[u]=++tot;
for(int i=h[u];i;i=e[i].nxt) {
int v=e[i].v;
if(v==p) continue;
dfs(v,u);
}
out[u]=tot;
}
struct Query{int l,x,id;} a[200005];
bool cmp(Query a1,Query a2) {return a1.l<a2.l;}
struct Binary_Indexed_Tree {
int t[100005];
int lb(int x) {return x&-x;}
int sum(int x) {int s=0;for(int i=x;i;i-=lb(i)) s+=t[i];return s;}
int query(int x,int y) {return sum(y)-sum(x-1);}
void add(int x,int k) {for(int i=x;i<=n;i+=lb(i)) t[i]+=k;}
} t;
signed main() {
cin>>tt;
while(tt--) {
n=rd(),q=rd();
memset(h,0,sizeof(h));tot=cnt=0;
memset(ans,0,sizeof(ans));
memset(t.t,0,sizeof(t.t));
for(int i=1;i<n;i++) {
int u=rd(),v=rd();
add(u,v),add(v,u);
}
dfs(1,0);
for(int i=1;i<=n;i++)
p[i]=rd();
for(int i=1;i<=q;i++) {
int l=rd(),r=rd(),x=rd();
a[i*2-1]={l-1,x,-i};
a[i*2]={r,x,i};
}
sort(a+1,a+q*2+1,cmp);
for(int i=0,j=1;i<=n;i++) {
if(i) t.add(in[p[i]],1);
for(;j<=q*2&&a[j].l==i;j++)
if(a[j].id>0) ans[a[j].id]+=t.query(in[a[j].x],out[a[j].x]);
else ans[-a[j].id]-=t.query(in[a[j].x],out[a[j].x]);
}
for(int i=1;i<=q;i++)
puts(ans[i]>0?"YES":"NO");
puts("");
}
return 0;
}