CF1899G Unusual Entertainment 题解

FFTotoro · 2023-11-28 21:03:13 · 题解

本题可以不需要用到那么多高深的数据结构，只需使用启发式合并。

先把树上所有点的编号变为该编号在排列中出现时的下标，这样每个询问就变成了查找是否存在编号在 [l,r] 的后代了。

直接使用 set 维护一个点的所有后代，至于怎么维护可以用启发式合并。每次找到重儿子直接 swap 到父亲上，剩下的用 merge 函数暴力合并。然后对于在该结点上的所有询问依次在 set 中二分查找判断即可。

时间复杂度是经典的启发式合并复杂度 O(n\log^2n)。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,q; cin>>n>>q;
    vector<pii> e(n-1);
    for(auto &[u,v]:e)cin>>u>>v; // 提前存边
    vector<int> p(n+1);
    for(int i=0;i<n;i++){
      int x; cin>>x; p[x]=i;
    } // 建立映射
    vector<vector<int> > g(n);
    for(auto &[u,v]:e){
      g[p[u]].emplace_back(p[v]);
      g[p[v]].emplace_back(p[u]);
    } // 建树
    vector<vector<tpi> > w(n);
    vector<bool> b(q);
    for(int i=0;i<q;i++){
      int l,r,x; cin>>l>>r>>x;
      w[p[x]].emplace_back(l-1,r-1,i);
    } // 离线所有询问
    vector<set<int> > s(n);
    function<void(int,int)> dfs=[&](int u,int f){
      int h=u; // h 是重儿子
      for(int i:g[u])
        if(i!=f)if(dfs(i,u);s[i].size()>s[h].size())h=i;
      if(h!=u)s[u].swap(s[h]); // 把重儿子的翻上来
      for(int i:g[u])
        if(i!=f&&i!=h)s[u].merge(s[i]); // 暴力合并
      s[u].emplace(u); // 加进它本身
      for(auto [l,r,i]:w[u])
        if(auto p=s[u].lower_bound(l);p!=s[u].end()&&*p<=r)b[i]=true;
        // 使用 lower_bound 进行二分查找
    };
    dfs(p[1],p[1]); // 注意此时的根是 p[1]！
    for(bool i:b)cout<<(i?"Yes\n":"No\n");
  }
  return 0;
}