传送门:CF
[前题提要]:没什么好说的,区域赛爆炸之后发愤加训思维题.秒了div3 A~F的脑筋急转弯,然后被G卡了,树剖dfs序的想法已经想到了,题目也已经化简为两个线段是否存在一个合法位置了.但是MD不会二维数点,用一个树剖+扫描线搞来搞去最后还是Tle.果然如下图所说:科技还是十分重要的.
首先读完题意.不难想到本题应该是一道数据结构题.因为对于 x x x的儿子节点我们是可以直接使用 d f s dfs dfs序或者树链剖分直接维护出来编号的.所以对于我们的每一个询问,相当于求出区间 [ l , r ] [l,r] [l,r]是否存在一个点,它的 d f s dfs dfs序在x的子孙节点中.
设我们维护出来的 x x x的子孙节点(包括他自己)区间为 [ L x , R x ] [L_x,R_x] [Lx,Rx](这里需要提一句的是对于一个节点的所有儿子来说,它的 d f s dfs dfs序一定是连续的,具体证明此处略).设一个点 u u u的 d f s dfs dfs,为 d f n ( u ) dfn(u) dfn(u).那么现在这道题就是问是否存在一个点在序列中的位置为 k ∈ [ l , r ] k\in[l,r] k∈[l,r],然后 d f n ( k ) ∈ [ L x , R x ] dfn(k)\in[L_x,R_x] dfn(k)∈[Lx,Rx].
额.当时我就卡在了这个维护上.但其实这是一个很模板的二维偏序(二维数点)问题.模板题指路
我们将
x
∈
[
l
,
r
]
x\in[l,r]
x∈[l,r]看成横坐标,将所有
d
f
n
(
x
)
dfn(x)
dfn(x)看成纵坐标.那么就是问你是否存在一个点
(
x
,
d
f
n
(
x
)
)
(x,dfn(x))
(x,dfn(x))在一个矩形区域内.这是一个很典型的二维数点问题.考虑将所有的询问矩形区域使用二维前缀和的思想进行化解,然后离线下来一个一个枚举,在枚举的过程中,将所有的点逐个加入到我们的树状数组中.只要保证所有点的横坐标小于当前询问区域,我们就可以将二维询问问题转化为一维询问,只要用树状数组维护一下就行了.
下面是具体的代码部分:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
inline void print(__int128 x){
if(x<0) {putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
#define maxn 200010
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
inline int lowbit(int x) {
return x&(~x+1);
}
int tree[maxn];int n,q;
void Add(int pos,int val) {
while(pos<=n) {
tree[pos]+=val;
pos+=lowbit(pos);
}
}
int Query(int pos) {
int ans=0;
while(pos) {
ans+=tree[pos];
pos-=lowbit(pos);
}
return ans;
}
vector<int>edge[maxn];
int in[maxn],out[maxn];int tot=0;
void dfs(int u,int per_u) {
in[u]=++tot;
for(auto v:edge[u]) {
if(v==per_u) continue;
dfs(v,u);
}
out[u]=tot;
}
int Ans[maxn];int p[maxn];
int main() {
int T=read();
while(T--) {
n=read();q=read();
for(int i=1;i<n;i++) {
int u=read();int v=read();
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;i++) {
p[i]=read();p[i]=in[p[i]];
}
vector<tuple<int,int,int,int> >Q;
for(int i=1;i<=q;i++) {
int l=read();int r=read();int x=read();
Q.push_back({l-1,in[x]-1,i,1});
Q.push_back({l-1,out[x],i,-1});
Q.push_back({r,in[x]-1,i,-1});
Q.push_back({r,out[x],i,1});
}
sort(Q.begin(),Q.end());
int cur=0;
for(auto [a,b,id,val]:Q) {
while(cur+1<=a) {
cur++;
Add(p[cur],1);
}
Ans[id]+=val*Query(b);
}
for(int i=1;i<=q;i++) {
cout<<(Ans[i]>0?"YES":"NO")<<endl;
}
tot=0;
for(int i=1;i<=n;i++) {
tree[i]=0;
edge[i].clear();in[i]=out[i]=0;
}
for(int i=1;i<=q;i++) {
Ans[i]=0;
}
}
return 0;
}