CF 2002 D1. DFS Checker (Easy Version) （*1900）思维

showball / 2024-09-02 / 原文

CF 2002 D1. DFS Checker (Easy Version) （*1900）思维

题目链接

题意：

给你一棵 $n$ 个节点组成的完全二叉树，并给出一个排列 $p$ 。接下来进行 $q$ 次询问。

每次询问给你 $x$ 和 $y$ ，你需要交换 $p_x$ 和 $p_y$。并且回答交换之后的排列 $p$ 是否是这棵

完全二叉树的DFS序。交换是持久的。

思路：

我们可以将每个节点在DFS序中的位置看做点权。那么我们发现对于每棵子树中的节点，它的点权一定是连续的。

由于是排列，不会重复，因此我们只需要比较最小值和最大值即可。这样每次判断每个节点即可。我们可以对每个节点维护其儿子的集合。

对于修改：我们直接暴力维护好set即可。

时间复杂度 $O(nlog^2n)$

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;

void Showball(){
   int n,q;
   cin>>n>>q;
   vector<int> e[n+1],fa(n+1),p(n+1),a(n+1);
   set<int> son[n+1];
   for(int i=1;i<=n;i++) e[i].clear(),son[i].clear();
   for(int i=2;i<=n;i++){
     cin>>fa[i];
     e[fa[i]].pb(i);
   }
   for(int i=1;i<=n;i++){
     cin>>p[i];
     a[p[i]]=i;
   }

   vector<int> sz(n+1);
   int cnt=0;

   auto check=[&](int u){
     return a[u]==*son[u].begin()&&a[u]+sz[u]-1==*son[u].rbegin();
   };

   function<void(int,int)> dfs=[&](int u,int father){
      sz[u]=1;son[u].insert(a[u]);
      for(auto v:e[u]){
        if(v==father) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        for(auto it:son[v]) son[u].insert(it); 
      }
      cnt+=check(u);
   };

   dfs(1,0);
   while(q--){
    int x,y;
    cin>>x>>y;
    swap(p[x],p[y]);
    x=p[x],y=p[y];
    vector<int> cand;
    for(int i=x;i;i=fa[i]) cand.pb(i);
    for(int i=y;i;i=fa[i]) cand.pb(i);
    sort(all(cand));
    cand.erase(unique(all(cand)),cand.end());
    for(auto it:cand) cnt-=check(it);
    for(int i=x;i;i=fa[i]) son[i].erase(a[x]);
    for(int i=y;i;i=fa[i]) son[i].erase(a[y]);
    swap(a[x],a[y]);
    for(int i=x;i;i=fa[i]) son[i].insert(a[x]);
    for(int i=y;i;i=fa[i]) son[i].insert(a[y]);
    for(auto it:cand) cnt+=check(it);
    cout<<(cnt==n?"Yes\n":"No\n");
   }

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}