CF1899G Unusual Entertainment 题解

harmis_yz · 2023-11-18 02:11:45 · 题解

分析

一眼树上启发式合并。

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