CF Gym101438F Tree Game

发表于 | 分类于

Description

有一个\(n\)个无色点的树，小红和小蓝二人在上面玩游戏。

游戏有很多轮，小红先手，然后两人轮替操作。每一轮操作者都必须将一个无色点染成自己的颜色，最后操作者的得分就是他自己染色的点的导出子图的连通块数量。

双方都想最大化自己和对方的得分差距，并且双方都一定采取最优策略。求最后小红和小蓝得分之差。

\(1\leq n\leq 2\times 10^5\)。

Solution

感觉算是套路题……？

考虑转化一下那个连通块的数量。我们考虑一个人，注意到我们可以先假设所有边都不存在，这样连通块数量为\(c_A\)（即\(A\)选的点数）。然后考虑把边加回来，注意到这个过程中那个导出子图始终是一个森林，所以最终的连通块数为\(c_A - e_A\)（\(e_A\)即两侧都被\(A\)选了的边）。

那么做一下差就知道最终的答案应该是\(c_A - c_B - e_A + e_B\)。由于每个人在自己的回合必须操作，所以\(c_A - c_B\)是一个定死的值。那么考虑\(-e_A + e_B\)，注意到我们可以把一条边对答案的影响\(1\)拆成两半放到点上，然后这样的话只有两边点都被一个人选了这个边才会被归成一个人的，反之则这条边不对答案产生影响。因此我们可以对点权排序，然后小红和小蓝轮流选点即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
const int maxn = 200005;
int deg[maxn];
int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    deg[u] ++; deg[v] ++;
  }
  std::sort(deg + 1, deg + 1 + n);
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    if(1 & i) {
      ans += deg[i];
    } else {
      ans -= deg[i];
    }
  }
  ans *= -1; ans /= 2;
  if(1 & n) ans ++;
  printf("%d\n", ans);
  return 0;
}