QOJ #5092. 森林游戏 题解

Description

小 A 和小 B 正在玩游戏。

他们面前有一个有根树森林，每个点 $u$ 有正整数点权 $A_u$。

小 A 和小 B 轮流操作，小 A 先手。当前操作的玩家需要选择恰好一个树根删除，获得它的点权，它的子树成为新的有根树，它的儿子成为新的树根。

所有点都删除后游戏结束，玩家的得分是由他删除的点权和。

两个玩家的目标都是最大化自己的得分，他们都采用最优策略。求最终小 A 的得分。

给定的初始局面包含恰好一棵 $n$ 个点的树，点编号从 $1$ 至 $n$，点 $1$ 为根。

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

Solution

首先每次贪心选择权值最大的根是不对的，因为如果一个比较大的点下面接了一个又大一个量级的东西，那么两个人一定会避开这个点，而按照之前的策略就一定会选到这个点。

但是容易发现在 $a_i\leq a_{p_i}$ 时候上面的做法是对的，考虑把一般情况转成上面的做法能做的形式。

把权值看成第一个人的总和减去第二个人的总和，第一个人要求最大化，第二个人要求最小化。

先考虑若干条链的情况。

对于一条链，如果其前三个点为 $x,y,z$，且 $a_x<a_y$。

引理 1：最优策略下第一个人选了 $x$ 之后，第二个人一定会选 $y$。

证明（感性）：一个人不选 $y$ 的理由是需要先选择权值更小的 $x$，而如果这时一个人主动把权值小的 $x$ 拿掉了，另一个人还不选 $y$ 就说明选 $x$ 是很不优的，第一个人直接选别的一定更好。

引理 2：最优策略下第一个人选 $x$，第二个人选 $y$ 后，第一个人会接着选 $z$。

证明（感性）：第一个人选择 $x$ 并获得一个负数权值，还不去选后面的 $z$ 不如一开始就选别的。

---

根据上面两个引理，一条链如果 $a_x<a_y$，则可以把前三个点的权值变为 $a_x-a_y+a_z$，成为一个更小的问题。如果合并到最后只剩两个点了，还是满足 $a_x<a_y$ 的话，就说明这两个点一定是最后解决，且是第一个人选了 $x$ 后第二个人接着选 $y$。贡献是 $(-1)^n(a_x-a_y)$。

如果所有链都满足权值不增的话，显然可以把所有权值归并起来，两个人按照顺序选。

回到原问题，我们考虑按照子树顺序从下往上做，容易发现每个子树一定是子问题。

假设 $u$ 的每个子树都合并成了一个不增的链，则可以把子树的链先归并起来，在开头加上 $a_u$。然后一直调整直到成为不增链或者最终只剩两个点后把贡献加到答案里即可。

用启发式合并+优先队列维护即可。

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

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 2e5 + 5;

int n, ans;
int a[kMaxN];
std::vector<int> G[kMaxN];
std::priority_queue<int> q[kMaxN];

void dfs(int u, int fa) {
  for (auto v : G[u]) {
    if (v == fa) continue;
    dfs(v, u);
    if (q[u].size() < q[v].size()) q[u].swap(q[v]);
    for (; !q[v].empty(); q[v].pop()) q[u].emplace(q[v].top());
  }
  for (; q[u].size() > 1 && a[u] < q[u].top();) {
    int x = q[u].top(); q[u].pop();
    int y = q[u].top(); q[u].pop();
    a[u] = a[u] - x + y;
  }
  if (q[u].size() == 1 && a[u] < q[u].top()) {
    ans += ((~n & 1) ? 1 : -1) * (a[u] - q[u].top());
    q[u].pop();
  } else {
    q[u].emplace(a[u]);
  }
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> a[i], ans += a[i];
  for (int i = 1; i < n; ++i) {
    int u, v;
    std::cin >> u >> v;
    G[u].emplace_back(v), G[v].emplace_back(u);
  }
  dfs(1, 0);
  for (int o = 1; !q[1].empty(); q[1].pop(), o = -o) ans += o * q[1].top();
  std::cout << ans / 2 << '\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;
}