CF2079C Dreaming Is Not Harmful 题解

· · 题解

Dreaming is not harmful.

有一个很重要的点：如果不考虑降低员工能力值，那么所有员工被开除的顺序是固定的。先处理出这个序列（可以使用优先队列维护这个过程），记 \mathrm{ord}(i) 为第 i 天当上 CEO 的员工编号。

接着观察到将一个员工的能力值降为 0，等价于删掉这个员工和他 / 她的所有下属（即忽略一棵子树）。假设员工 u 满足 \mathrm{ord}(p)=u，那么只有员工 \mathrm{ord}(1),\mathrm{ord}(2),\ldots,\mathrm{ord}(p-1) 可能影响到他 / 她。只需要选择一棵子树（当然这棵子树不能包含 u），使得其中包含尽可能多的上述员工，进行删除后的答案就是最优的。

维护一棵带权树 T：顺次求解 \mathrm{ord}(1),\mathrm{ord}(2),\ldots,\mathrm{ord}(n) 的答案，设当前考虑到的员工编号为 u，那么每次求解结束后就将 T 中 u 到根的路径上所有点权值 +1；于是查询最大子树和变为单点权值，就可以用树链剖分 + 线段树维护。

注意特别处理“子树不能包含 u”的限制：考虑一个极大值 I（可以取 I=10^{18}），只需要在求解前将 u 到根的链上点的权值都减去 I，求解后再加上 I 即可。

时间复杂度 O(n\log^2n)。

代码中为了方便实现，直接将员工编号替换为其能力值。放代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int I=1e9;
class segtree{
  private:
    vector<pii> B;
    vector<ll> S,T;
    inline void pushup(int u){
      S[u]=max(S[u<<1],S[u<<1|1]);
    }
    inline void pushdown(int u){
      if(T[u]){
        S[u<<1]+=T[u],S[u<<1|1]+=T[u];
        T[u<<1]+=T[u],T[u<<1|1]+=T[u],T[u]=0;
      }
    }
  public:
    segtree(int n):B(n<<2),S(n<<2),T(n<<2){
      function<void(int,int,int)> build=[&](int u,int l,int r){
        if(B[u]=make_pair(l,r);l==r)return;
        int m=l+r>>1;
        build(u<<1,l,m),build(u<<1|1,m+1,r);
      };
      build(1,0,n-1);
    }
    void update(int u,int l,int r,int d){
      if(B[u].first>r||B[u].second<l)return;
      if(l<=B[u].first&&B[u].second<=r){
        S[u]+=d,T[u]+=d; return;
      }
      pushdown(u);
      update(u<<1,l,r,d),update(u<<1|1,l,r,d);
      pushup(u);
    }
    inline int all_prod(){return S[1];}
}; // 线段树
class hld{
  private:
    int n;
    vector<int> f,e,h,t,l;
    segtree T;
  public:
    hld(int rt,vector<vector<int> > g):n(g.size()),T(n){
      f.resize(n),e.resize(n,1);
      h.resize(n,-1),t.resize(n),l.resize(n);
      function<void(int)> dfs=[&](int u){
        int mx=0;
        for(int i:g[u]){
          f[i]=u,dfs(i),e[u]+=e[i];
          if(e[i]>mx)mx=e[i],h[u]=i;
        }
      };
      int o=0;
      function<void(int,bool)> decomp=[&](int u,bool b){
        t[u]=b?t[f[u]]:u,l[u]=o++;
        if(~h[u])decomp(h[u],true);
        for(int i:g[u])
          if(i!=h[u])decomp(i,false);
      };
      f[rt]=-1,dfs(rt),decomp(rt,false);
    }
    inline void update(int u,int d){
      while(~u)T.update(1,l[t[u]],l[u],d),u=f[t[u]];
    } // 链加
    inline int query(){return T.all_prod();} // 全局 max
}; // 树链剖分
int main(){
  ios::sync_with_stdio(false);
  int n,m; cin>>n>>m;
  vector<pii> e;
  for(int i=1;i<n;i++){
    int f; cin>>f;
    e.emplace_back(f-1,i);
  }
  vector<int> s(n),o,r(n);
  for(auto &i:s)cin>>i,i--;
  vector<vector<int> > g(n);
  for(auto [u,v]:e)
    g[s[u]].emplace_back(s[v]);
  priority_queue<int> q;
  q.emplace(s[0]);
  while(!q.empty()){
    int u=q.top(); q.pop();
    o.emplace_back(u);
    for(int i:g[u])q.emplace(i);
  } // 求解原顺序
  hld h(s[0],g);
  for(int i=0;i<n;i++){
    int u=o[i];
    h.update(u,-I);
    r[u]=i-max(0,h.query());
    h.update(u,I+1);
  } // 依次求解
  while(m--){
    int x; cin>>x;
    cout<<r[s[x-1]]<<' ';
  }
  cout<<endl;
  return 0;
}