「ZJOI2018」历史题解

2020-05-10

题目链接: https://uoj.ac/problem/374

一道非常有意思的 Link-Cut Tree 题.

~~ZJOI2018 唯一可做题~~

题意简述

给定一棵有 $n$ 个节点的树, 根节点为 $1$. 在该树基础上建立 LCT, 同时给出第 $i$ 个点 access 的次数为 $a_i$. $m$ 次修改, 修改为将 $a_{x_i}$ 的值增加 $w_i$.

分别求出初始状态下, 和 $m$ 次修改后, access 操作中改变虚实链次数总和的最大值.

其中, $n,m \le 4 \times 10 ^ 5, a_i, w_i \le 10 ^ 7$.

解题思路

先考虑不带修改怎么做.

首先每个点 access 操作时只会影响该点到根节点路径上的点, 因此影响一个点到其儿子边的虚实的操作只会发生在该点的子树内. 所以将每个子树分开考虑, 统计答案时直接求和即可.

注意到来自同一子树内的连续两次 access 操作, 并不会改变该子树根 $v$ 到 $v$ 的父亲 $u$ 这条边的虚实. 记 $u$ 的 access 次数为 $A_0$, 其儿子 $v$ 的子树内部 access 次数和分别为 $A_i$, 且节点 $u$ 共有 $m$ 个儿子. 那么问题可转化为

给定若干个球, 总共有 $0$ 到 $m$ 共 $m + 1$ 种颜色, 第 $i$ 种颜色的球有 $A_i$ 个.

现在要构造一种球的排列, 使得相邻两个球颜色不同的间隔数尽量多.

有一个贪心的思路: 选择小球个数最多的颜色, 将这些小球排成一列. 同时将其余小球插入这列小球之间. 用更加形式化的语言可描述为

记 $h = \max\limits_{i = 0} ^ m \{A_i \}$, $t = \sum\limits_{i = 0} ^ m A_i$, 分两种情况讨论.

$2h \le t$, 此时答案为 $t - 1$.

即所有的小球中存在至多一半的球有相同颜色.
$2h \ge t + 1$, 此时答案为 $2 (t - h)$.

此种情况下按照上述策略贪心, 则不可避免存在多出一部分相同颜色的小球. 无论怎样改变已经放置的小球, 都无法使得不同颜色小球间隔数增加. 统计放置这些相同颜色小球前的间隔数, 即可计算答案.

也就是 $\min \{ t - 1, 2(t - h) \}$.

因而可以得到一个做法: 直接 DFS 整棵树, 分别统计每棵子树对答案贡献. 可以在 $O(n)$ 的时间复杂度内计算.

观察上述结论中两种情况的性质. 设 $s_u$ 为 $u$ 子树内的 access 次数之和.

对于带修改的情况, 对于一条边 $(u, fa)$, 将满足 $2s_u \ge s_{fa} + 1$ 的边视作实链, 否则视为虚链. 类比于重链剖分, 虚链的个数有 $O(\log \sum a_i) = O(\log n)$ 个, 且连向 $fa$ 的实链唯一, 实儿子一定是 $u$.

对于一条实链, 每次单点修改 $u$ 的值时, $fa$ 处的答案不会改变: 此时 $h$ 的值不会发生变化, 且 $t - h$ 的差值不变.

可以直接用 LCT 来维护, 每次修改后暴力 access 沿当前点到根的路径依次修改即可. 注意实现时的细节, 以及虚实链的改变需要遵循上述条件.

时间复杂度 $O(n \log n)$.

代码实现

// UOJ #374
// DeP
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define DEBUG(args...) fprintf(stderr, ##args)

namespace IO {
  const int MAXSIZE = 1 << 18 | 1;
  char buf[MAXSIZE], *p1, *p2;

  inline int Gc() {
    return p1 == p2 &&
      (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
  }
  template<typename T> inline void read(T& x) {
    x = 0; int f = 0, ch = Gc();
    while (!isdigit(ch)) f |= ch == '-', ch = Gc();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
    if (f) x = -x;
  }
}
using IO::read;

template<typename T> inline bool ckmax(T& a, const T& b) {
  return (a < b)? a = b, true: false;
}

typedef long long LL;
const int MAXN = 4e5 + 5;

int n, q;
LL ans;

namespace LCT {
  int ch[2][MAXN], pre[MAXN];
  LL s[MAXN], is[MAXN], val[MAXN];

  inline void maintain(const int& nd) {
    s[nd] = is[nd] + val[nd];
    if (ch[0][nd]) s[nd] += s[ch[0][nd]];
    if (ch[1][nd]) s[nd] += s[ch[1][nd]];
  }

  inline int which(const int& u) { return pre[u]? ch[1][pre[u]] == u: 0; }
  inline bool nroot(const int& u) {
    return pre[u]? ch[0][pre[u]] == u || ch[1][pre[u]] == u: false;
  }

  inline void rotate(const int& u) {
    int fa = pre[u], w = which(u);
    pre[u] = pre[fa];
    if (nroot(fa)) ch[which(fa)][pre[fa]] = u;
    ch[w][fa] = ch[w ^ 1][u];
    if (ch[w ^ 1][u]) pre[ch[w ^ 1][u]] = fa;
    ch[w ^ 1][u] = fa, pre[fa] = u;
    maintain(fa);
  }

  void splay(const int& u) {
    while (nroot(u)) {
      int fa = pre[u];
      if (nroot(fa)) which(fa) == which(u)? rotate(fa): rotate(u);
      rotate(u);
    }
    maintain(u);
  }

  inline LL calc(int u, LL t, LL h) {
    if (ch[1][u]) return 2 * (t - h);
    if (2 * val[u] >= t + 1) return 2 * (t - val[u]);
    return t - 1;
  }

  void access(int u, const int& w) {
    int v = u;
    for (u = pre[u]; u; v = u, u = pre[u]) { // start from pre[u]
      splay(u);
      LL t = s[u] - s[ch[0][u]], h = s[ch[1][u]];
      ans -= calc(u, t, h);
      s[u] += w, t += w, is[u] += w;
      if (2 * h < t + 1)
        ch[1][u] = 0, is[u] += h;
      if (2 * s[v] >= t + 1) // update weight son
        ch[1][u] = v, h = s[v], is[u] -= h;
      ans += calc(u, t, h);
      maintain(u);
    }
  }

  void Mdy(int u, const int& w) {
    splay(u);
    LL t = s[u] - s[ch[0][u]], h = s[ch[1][u]];
    ans -= calc(u, t, h);
    val[u] += w, t += w, s[u] += w;
    if (2 * h < t + 1)
      ch[1][u] = 0, is[u] += h;
    ans += calc(u, t, h);
    maintain(u), access(u, w);
  }
}

namespace Graph {
  struct Edge { int nxt, to; } edges[MAXN << 1];
  int head[MAXN], eidx;

  inline void init() { memset(head, -1, sizeof head), eidx = 1; }
  inline void AddEdge(int from, int to) {
    edges[++eidx] = (Edge){ head[from], to }, head[from] = eidx;
  }

  void dfs(int u) {
    using namespace LCT;
    int rson = -1;
    LL &t = s[u], h = val[u]; t = val[u];
    for (int v, i = head[u]; ~i; i = edges[i].nxt) {
      if ((v = edges[i].to) == pre[u]) continue;
      pre[v] = u, dfs(v), t += s[v];
      if (ckmax(h, s[v])) rson = v;
    }
    ans += min(t - 1, 2 * (t - h));
    if (rson > 0 && 2 * h >= t + 1)
      ch[1][u] = rson, is[u] = s[u] - s[rson] - val[u];
    else
      is[u] = s[u] - val[u];
  }
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("data/ex_history2.in", "r", stdin);
#endif
  Graph::init();

  read(n), read(q);
  for (int i = 1; i <= n; ++i) read(LCT::val[i]);
  for (int u, v, i = 1; i < n; ++i)
    read(u), read(v), Graph::AddEdge(u, v), Graph::AddEdge(v, u);

  Graph::dfs(1), printf("%lld\n", ans);

  for (int x, w; q; --q) {
    read(x), read(w), LCT::Mdy(x, w);
    printf("%lld\n", ans);
  }
  return 0;
}

参考资料

ZJOI2018 day1 solution by ???
Kelin, [ZJOI2018]历史

DepletedPrism's Blog

「ZJOI2018」历史 题解

题意简述

解题思路

代码实现

参考资料

「ZJOI2018」历史题解