P5773 [JSOI2016] 轻重路径 题解

Description

在二叉树上，不断删除叶子，你要维护其重链剖分后重儿子编号和。如果两个孩子大小相同，在一开始连向左儿子，后面保持修改前的连接。

$n\leq 2\times 10^5$。

Solution

考虑把一个叶子 $x$ 删掉会对改变哪些点的重儿子。

首先改变的点 $y$ 一定在 $x$ 到根的链上，同时要求 $sz_y\leq\frac{sz_{fa_y}}{2}$。

那么不妨设当前从上到下修改到 $rt$，则 $sz_y\leq\frac{sz_{fa_y}}{2}\leq\frac{sz_{rt}}{2}$，可以通过倍增找到链上最上面的满足 $sz_y\leq\frac{sz_{rt}}{2}$ 的 $y$，暴力判断 $y$ 能否被修改然后将 $rt$ 设为 $y$ 继续找即可。

由于有 $O(n\log^2n)$ 次查询子树大小的操作，直接树状数组为 $O(n\log^3n)$，用分块 $O(1)$ 求区间和即可做到 $O(n\log^2n+n\sqrt n)$。

时间复杂度：$O(n\log^3n)/O(n\log^2n+n\sqrt n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 2e5 + 5;

int n, m, lg;
int64_t sum;
int a[kMaxN], p[kMaxN][19], dfn[kMaxN], sz[kMaxN], wson[kMaxN];
int L[kMaxN], R[kMaxN];
std::vector<int> G[kMaxN];

struct BIT {
  int c[kMaxN];

  void upd(int x, int v) {
    for (; x <= n; x += x & -x) c[x] += v;
  }
  int qry(int x) {
    int ret = 0;
    for (; x; x -= x & -x) ret += c[x];
    return ret;
  }
  int qry(int l, int r) { return l <= r ? qry(r) - qry(l - 1) : 0; }
} bit;

int getsz(int x) {
  if (!x) return 0;
  else return bit.qry(dfn[x], dfn[x] + sz[x] - 1);
}

void dfs(int u, int fa) {
  static int cnt = 0;
  dfn[u] = ++cnt, sz[u] = 1, p[u][0] = fa;
  for (int i = 1; i <= lg; ++i) p[u][i] = p[p[u][i - 1]][i - 1];
  for (auto v : G[u]) {
    if (v == fa) continue;
    dfs(v, u);
    sz[u] += sz[v];
    if (sz[v] > sz[wson[u]]) wson[u] = v;
  }
  sum += wson[u];
}

void update(int x) {
  bit.upd(dfn[x], -1);
  int rt = 1;
  for (; rt != x;) {
    int y = x, now = getsz(rt);
    for (int i = lg; ~i; --i)
      if (p[y][i] && getsz(p[y][i]) <= getsz(rt) / 2)
        y = p[y][i];
    int fa = p[y][0];
    if (y == wson[fa]) {
      int z = L[fa] + R[fa] - y;
      if (getsz(z) > getsz(y)) sum -= y, wson[fa] = z, sum += z;
    }
    rt = y;
  }
  if (x == wson[p[x][0]]) sum -= x;
}

void dickdreamer() {
  std::cin >> n;
  lg = std::__lg(n);
  for (int i = 1; i <= n; ++i) {
    std::cin >> L[i] >> R[i];
    if (L[i]) G[i].emplace_back(L[i]);
    if (R[i]) G[i].emplace_back(R[i]);
  }
  dfs(1, 0);
  std::cin >> m;
  for (int i = 1; i <= n; ++i) bit.upd(i, 1);
  std::cout << sum << '\n';
  for (int i = 1; i <= m; ++i) {
    int x;
    std::cin >> x;
    update(x);
    std::cout << sum << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}