P5773 [JSOI2016] 轻重路径

_zdc_ · 2023-12-02 14:33:58 · 题解

定义 dif_i=size_{L_i}-size_{R_i}。

注意到每次删叶子对 dif 的影响是 1 或 -1，所以删 B 次叶子后只有满足 |dif_i| \le B 的点 i 的重儿子可能改变。称这种点为关键点。

删掉 x 时，考虑找 x 的祖先中所有关键点并修改 dif。这一部分是 O(QB) 的。

因为每 B 次操作后需要 O(N) 重新算 dif 等信息，所以这一部分是 O(\dfrac{NQ}{B}) 的。

取 B=\sqrt N，时间复杂度 O(Q\sqrt N)。实测取 B=3500 最快。

#include <bits/stdc++.h>
#define All(x, l, r) &x[l], &x[r + 1]
#define ALL(x) begin(x), end(x)
using namespace std;
void file(){
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
}
using ll = long long;
const int nMax = 2e5 + 5, Lim = 3503;
int n, q;
array<int, nMax> p, sz, l, r, f, fa, hvy, dif;
array<bool, nMax> lr;
void reb(){
  for(int i = n; i; i--) sz[i] = sz[l[i]] + sz[r[i]] + 1;
  for(int i = 1; i <= n; i++){
    int x = fa[i];
    if(abs(dif[i] = sz[l[i]] - sz[r[i]]) <= Lim) x = i;
    fa[l[i]] = fa[r[i]] = x;
    if(x == i){ lr[l[i]] = 0; lr[r[i]] = 1; }
    else lr[l[i]] = lr[r[i]] = lr[i];
  }
}
int main(){
  // file();
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> l[i] >> r[i];
    fa[l[i]] = fa[r[i]] = i;
  }
  f = fa; cin >> q;
  for(int i = 1; i <= q; i++) cin >> p[i];
  for(int i = n; i; i--){
    sz[i] = sz[l[i]] + sz[r[i]] + 1;
    hvy[i] = (sz[l[i]] >= sz[r[i]]) ? l[i] : r[i];
  }
  ll res = accumulate(All(hvy, 1, n), 0ll);
  cout << res << "\n";
  for(int i = 1; i <= q; i++){
    if(i % 3500 == 1) reb();
    int v = p[i], t = f[v]; res -= hvy[v];
    (l[t] == p[i]) && (l[t] = 0);
    (r[t] == p[i]) && (r[t] = 0);
    for(int ls = v, x = fa[v]; x; ls = fa[ls], x = fa[x]){
      bool f = lr[ls];
      f ? dif[x]++ : dif[x]--;
      res -= hvy[x];
      if((!dif[x]) && (!l[x]) && (!r[x])) hvy[x] = 0;
      if(dif[x] > 0) hvy[x] = l[x];
      if(dif[x] < 0) hvy[x] = r[x];
      res += hvy[x];
    }
    cout << res << "\n";
  }
  return 0;
}