CF1797D Li Hua and Tree 题解

· · 题解

前言

难得一好水 *1900……

警示后人：翻译中说的“点数”指的是子树大小，我开始时把这玩意读错了，WA 了 2 发……

解法

本题需要使用 STL std::set 维护树上操作。

符号规定：记一个结点 x 的父亲为 f_x，子树大小为 e_x，子树和为 s_x。

先跑一遍预处理 dfs，把还未进行任何操作时所有结点的父亲、子树大小、子树和算出来，便于后续维护。

接着对于每个结点开一个 set，set 中每个元素代表它的一个儿子 x，里面存一个二元组 pair，第一关键字存的是该儿子的子树大小 e_x（但是因为 set 默认比较方式是 less<>，所以较小的元素会排在前，插入时对 e_x 取一个相反数即可），第二关键字即为该儿子的结点编号 x。

对于每一次操作，如果是操作 1，直接输出 s_x，否则执行以下的算法流程：

  1. 找出 x 的重儿子（即 set 中存储的第一个元素），记为 h；

  2. 从 x 的 set 中删除 h；

  3. 从 f_x 的 set 中删除 x；

  4. 更改 e_x,e_h,s_x,s_h，具体地：

  5. 在 h 的 set 中加入 x；

  6. 在 f_x 的 set 中加入 h；

  7. 更改 f_x 和 f_h。

注意，以上的流程顺序不可以更改，把有些操作安排在前更便于引用未更改的信息。

时间复杂度 O(n+m\log n)，可以通过本题。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> g[100001];
set<pair<int,int> > k[100001];
int a[100001],s[100001],e[100001],f[100001];
void dfs(int u,int r){
  s[u]=a[u],e[u]=1,f[u]=r;
  for(int i:g[u])
    if(i!=r){
      dfs(i,u),s[u]+=s[i],e[u]+=e[i];
      k[u].emplace(-e[i],i);
    }
} // dfs 预处理所有信息
main(){
  ios::sync_with_stdio(false);
  int n,m; cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<n;i++){
    int u,v; cin>>u>>v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  dfs(1,0);
  while(m--){
    int op,x; cin>>op>>x;
    if(op==1)cout<<s[x]<<endl;
    else if(!k[x].empty()){
      int h=k[x].begin()->second;
      k[f[x]].erase(make_pair(-e[x],x));
      k[x].erase(make_pair(-e[h],h));
      e[x]-=e[h],e[h]+=e[x],s[x]-=s[h],s[h]+=s[x];
      k[h].emplace(-e[x],x);
      k[f[h]=f[x]].emplace(-e[h],h);
      f[x]=h;
    } // 按上面的流程模拟
  }
  return 0;
}