CF868E Policeman and a Tree

感觉，好自然啊！

想法 dp，想办法分解这个博弈的过程。发现警察会从一片叶子到另一片叶子，在叶子抓住小偷时所有小偷可以全树乱走。因此 dp：\(f_{u, i}\) 表示警察位于 \(u\)，全树剩余 \(i\) 个小偷时的答案。

因为两边都绝对理性，小偷在警察离开叶子后不会移动并位于多片叶子上。考虑小偷的决策确定之后的情况。警察要枚举叶片 \(v\)，转移形如 \(f_{u, x} = \min\{f_{v, x-i} + dis(u, v)\}\)，\(i\) 是 \(v\) 处小偷的个数。小偷需要最大化这个值。

转移可以用背包，也可以直接二分答案。二分答案时，每片叶子上小偷的数目有上限，加起来看是否大于等于 \(x\) 就行了。

对于小偷有初始情况，不过是出现了多棵子树，小偷不能全树跑。故每片叶子上小偷的数目的上限会不大一样。用一样的方法做就行了。

我们当时，不明白如何处理双方绝对理性这个条件。如今看来，不过是交替转移。能确定一方的策略后，另一方让其最劣，也是可以的。

#include <bits/stdc++.h>

const int inf = 1e9 + 7;

int main() {
  int n, s, m; scanf("%d", &n);
  std::vector<std::vector<int>> dis(n, std::vector<int> (n, inf));
  std::vector<std::vector<std::pair<int, int>>> e(n);
  std::vector<int> deg(n), siz(n);
  for (int i = 1, u, v, w; i < n; i++) {
    scanf("%d %d %d", &u, &v, &w), --u, --v;
    dis[u][v] = dis[v][u] = w, ++deg[u], ++deg[v];
    e[u].push_back({v, w}), e[v].push_back({u, w});
  }
  for (int i = 0; i < n; i++)
    dis[i][i] = 0;
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
  scanf("%d %d", &s, &m), --s;
  for (int i = 0, u; i < m; i++) scanf("%d", &u), --u, ++siz[u];
  std::vector<std::vector<int>> f(n, std::vector<int> (m + 1));
  std::vector<int> leaf;
  for (int i = 0; i < n; i++) if (deg[i] == 1) leaf.push_back(i);
  auto chk = [&](int u, int x, int lim) -> bool {
    int sum = 0;
    for (auto v : leaf) if (v != u) {
      int p = x;
      for (; p >= 1 && f[v][x - p] + dis[u][v] < lim; --p) ;
      sum += p;
    }
    return sum >= x;
  } ;
  for (int j = 1; j <= m; j++) {
    for (auto u : leaf) {
      int l = 0, r = 1e9; 
      while (l <= r) {
        int mid = l + r >> 1;
        if (chk(u, j, mid)) f[u][j] = mid, l = mid + 1;
        else r = mid - 1;
      }
    }
  }
  std::vector<int> bl(n);
  auto dfs = [&](auto self, int u, int f) -> void {
    for (auto [v, w] : e[u]) if (v != f) 
      bl[v] = bl[u], self(self, v, u), siz[u] += siz[v];
  } ;
  for (auto [u, w] : e[s]) bl[u] = u, dfs(dfs, u, s);
  auto chk2 = [&](int lim) -> bool {
    std::vector<int> res(n);
    int sum = 0;
    for (auto [u, w] : e[s]) res[u] = siz[u];
    for (auto u : leaf) if (u != s) {
      int j = res[bl[u]];
      for (; j && dis[s][u] + f[u][m - j] < lim; --j) ;
      sum += j, res[bl[u]] -= j;
    }
    return sum >= m;
  } ;
  int l = 0, r = 1e9, ans = 0;
  while (l <= r) {
    int mid = l + r >> 1;
    if (chk2(mid)) ans = mid, l = mid + 1;
    else r = mid - 1;
  }
  printf("%d\n", ans);
}