树学

Solution

十分简单的换根dp。

首先随便选择一个点作为根，计算出它的结果；

考虑它的一个相邻结点作为根时的结果与之间的关系：
当根从转移到时，子树内的点到根的距离减少、子树外的点到根的距离增加，
如果设为以为根时的子树大小，那么。

按照式子暴力dfs转移即可，复杂度。

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct edge {
  int v, nxt;
};

vector<edge> G;
int n, size[1000002], h[1000002];
ll ans, cur;

void addedge(int u, int v) {
  G.push_back({ v, h[u] }), h[u] = (int) G.size() - 1;
}

void dfs(int u, int f) {
  size[u] = 1;
  for (int i = h[u]; ~i; i = G[i].nxt) {
    const int& v = G[i].v;
    if (v != f) {
      dfs(v, u);
      size[u] += size[v];
    }
  }
  ans = (cur += size[u] - 1);
}

void solve(int u, int f) {
  ans = min(ans, cur);
  for (int i = h[u]; ~i; i = G[i].nxt) {
    const int& v = G[i].v;
    if (v != f) {
      cur = cur + n - 2 * size[v];
      solve(v, u);
      cur = cur - n + 2 * size[v];
    }
  }
}

int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  cin >> n;
  fill(h + 1, h + 1 + n, -1);
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    addedge(x, y), addedge(y, x);
  }
  dfs(1, -1), solve(1, -1);
  cout << ans << "\n";
}