P2726 [SHOI2005] 树的双中心 题解

Description

$n\leq 5\times 10^4$，树的深度 $\leq 100$。

Solution

对于每个 $x,y$，满足 $d(v,x)\leq d(v,y)$ 或者 $d(v,x)\geq d(v,y)$ 的点一定构成一个子树，所以可以枚举这个子树的根，然后对两边分别求重心可以得到答案。

但是直接暴力求是 $O(n^2)$ 的，过不了。

注意到深度很小，所以可以考虑 $O(h)$ 求一颗树的重心。

设 $sz_i$ 表示以 $i$ 为根的子树权值的和，假设已知节点 $u$ 到其他点的距离和 $now$，那么对于 $u$ 的儿子 $v$ 的答案就是 $now+sz_{root}-2\times sz_v$，所以每次只用跳到子树权值最大的儿子 $v$，如果答案不会变优就终止即可。

容易想到预处理每个点权值最大的儿子，但是这里求总树去掉当前树的连通块的答案时有修改，又注意到一个点最多只有一个儿子的权值会变，所以只要记录权值最大和次大的儿子即可。

时间复杂度：$O(nh)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 5e4 + 5;

int n;
int64_t ans = 1e18, sz[kMaxN], f[kMaxN];
int a[kMaxN], p[kMaxN], dep[kMaxN], wson1[kMaxN], wson2[kMaxN];
std::vector<int> G[kMaxN];

void dfs1(int u, int fa) {
  sz[u] = a[u], p[u] = fa, dep[u] = dep[fa] + 1;
  for (auto v : G[u]) {
    if (v == fa) continue;
    dfs1(v, u);
    sz[u] += sz[v], f[u] += f[v] + sz[v];
    if (sz[v] >= sz[wson1[u]]) wson2[u] = wson1[u], wson1[u] = v;
    else if (sz[v] >= sz[wson2[u]]) wson2[u] = v;
  }
}

int64_t dfs2(int u, int fa, int64_t now, int64_t sum, int pos) { // 找答案
  int v = wson1[u];
  if (v == pos || sz[wson2[u]] > sz[v]) v = wson2[u];
  if (sz[v] * 2 > sum) return std::min(now, dfs2(v, u, now + (sum - sz[v] * 2), sum, pos));
  else return now;
}

void dfs3(int u, int fa) {
  for (auto v : G[u]) {
    if (v == fa) continue;
    for (int j = u; j; j = p[j]) sz[j] -= sz[v];
    ans = std::min(ans, dfs2(v, u, f[v], sz[v], v) + dfs2(1, 0, f[1] - f[v] - (int64_t)(dep[v] - 1) * sz[v], sz[1], v));
    for (int j = u; j; j = p[j]) sz[j] += sz[v];
    dfs3(v, u);
  }
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v;
    std::cin >> u >> v;
    G[u].emplace_back(v), G[v].emplace_back(u);
  }
  for (int i = 1; i <= n; ++i)
    std::cin >> a[i];
  dfs1(1, 0), dfs3(1, 0);
  std::cout << ans << '\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;
}