CF1899G Unusual Entertainment 题解

分析

一眼树上启发式合并。

定义 \(x_i\) 为节点 \(i\) 在序列 \(p\) 中的下标。则问题转化为：对于每组 \(l,r,k\)，询问以 \(k\) 为根的子树中是否有一个以上的节点，满足 \(l \le x_j \le r\)。

使用 set 存以 \(i\) 为根的子树中 \(x_j\) 的有序排列。则对于每个 \(k=i\) 的询问，去合并之后的 set 中二分查找即可。树上启发式合并的话套版子就行了，只是多加了一个更新询问答案的过程而已。

注：模板题可以参照这道。但该模板题难度评级显然有问题。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define PII pair<int,pair<int,int>>
#define x first
#define y second

const int N=1e5+10;
int n,q;
int ne[N<<1],e[N<<1],h[N],idx;
struct node{
	set<int> st;
	vector<PII> Q;
	il int size(){return st.size();}
}sub[N];int x[N],id[N],cnt;
int ans[N];

il void add(int a,int b){ne[++idx]=h[a],e[idx]=b,h[a]=idx;}
il void dfs(int now,int fa){
	int mson=-1,msiz=0;
	id[now]=++cnt;
	for(re int i=h[now];i;i=ne[i]){
		int j=e[i];if(j==fa) continue;
		dfs(j,now);
		if(sub[id[j]].size()>msiz) msiz=sub[id[j]].size(),mson=j;
	}
	if(mson!=-1) id[now]=id[mson];
	for(re int i=h[now];i;i=ne[i]){
		int j=e[i];if(j==fa||j==mson) continue;
		for(auto s:sub[id[j]].st) sub[id[now]].st.insert(s);
		sub[id[j]].st.clear();
	}
	sub[id[now]].st.insert(x[now]);
	for(auto i:sub[now].Q){
		auto j=sub[id[now]].st.lower_bound(i.y.x);
		ans[i.x]=(j!=sub[id[now]].st.end()&&(*j)<=i.y.y);
	}
	return ;
}

il void solve(){
	cin>>n>>q;
	for(re int i=1;i<=n;++i) h[i]=ans[i]=x[i]=id[i]=0,sub[i].Q.clear(),sub[i].st.clear();
	idx=cnt=0;
	for(re int i=1,a,b;i<n;++i) cin>>a>>b,add(a,b),add(b,a);
	for(re int i=1,s;i<=n;++i) cin>>s,x[s]=i;
	for(re int i=1,l,r,x;i<=q;++i) cin>>l>>r>>x,sub[x].Q.push_back({i,{l,r}});
	dfs(1,0);
	for(re int i=1;i<=q;++i)
		if(ans[i]) cout<<"YES\n";
		else cout<<"NO\n";
	return ;
}

signed main(){
	int t;cin>>t;while(t--)
	solve();
	return 0;
}