题意：多次查询，每次给你数组的一个区间，和树上的一个点\(x\)，问数组这个区间有没有\(x\)的子节点。
题解：
树上每个点子节点的dfs序一定大于它，并且，可以处理出每个节点，子节点dfs序的区间。
问题转化成，所查询区间有没有值在区间【xl,xr】的，可持久化树状数组，可以实现，但是会很麻烦，
考虑用树状数组解决，对查询离线处理；
代码：
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pll;
typedef tuple<int,int,int> TP;
const int N = 1e6 + 10;
int a[N];
int n,m;
vector<int> ve[N];
int w=1;
pair<int,int> p[N];//子节点的dfs序
void dfs(int x,int f) //dfs处理dfs序，和字节点的区间
{
p[x].first=w;
for(auto v:ve[x])
{
if(v==f) continue;
w++;
dfs(v,x);
}
p[x].second=w;
}
vector<TP> la[N];
vector<TP> ra[N];
int ans[N];
int tr[N];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int k)
{
while(x<=n)
{
tr[x]+=k;
x+=lowbit(x);
}
}
int ser(int x)
{
int ans=0;
while(x>0)
{
ans+=tr[x];
x-=lowbit(x);
}
return ans;
}
void init()
{
for(int i=1;i<=n;i++) ve[i].clear();
w=1;
for(int i=1;i<=n;i++)
{
la[i].clear();
ra[i].clear();
tr[i]=0;
}
}
void solve(){
cin>>n>>m;
init();
int l,r,x;
for(int i=1;i<n;i++)
{
cin>>l>>r;
ve[l].push_back(r);
ve[r].push_back(l);
}
dfs(1,-1);
for(int i=1;i<=n;i++)
{
cin>>x;
a[i]=p[x].first; //数组节点转化成对应的dfs序
}
int xl,xr;
for(int i=1;i<=m;i++)
{
cin>>l>>r>>x;
xl=p[x].first;
xr=p[x].second;
//i为查询时间，xl，xr为查询节点的dfs序，
la[l].push_back({i,xl,xr});
ra[r].push_back({i,xl,xr});
}
//核心思路对于每个要查询的数组区间，先查询未放节点，在查询放完节点
//两者相减不为0，则表示，数组l,r之间，有dfs序未【xl,xr】 的，既子节点存在
for(int i=1;i<=n;i++)
{
for(auto [d,l,r]:la[i])
{
ans[d]=ser(r)-ser(l-1);
}
x=a[i];
add(x,1);
for(auto [d,l,r]:ra[i])
{
ans[d]-=(ser(r)-ser(l-1));
}
}
for(int i=1;i<=m;i++)
{
if(ans[i]<0)
{
cout<<"YES\n";
}
else cout<<"NO\n";
ans[i]=0;
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0 ^ 0;
}