ABC302Ex Ball Collector 题解

注意到当有那些 \((a_i,b_i)\) 是确定的时，答案就是将 \((a_i,b_i)\) 连边后每个连通块的 \(\min(|V|,|E|)\) 之和。

那么这个东西用可撤销并查集维护即可。

#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 2e5;

struct Edge {
  int to, nxt;
} e[N * 2 + 10];
int head[N + 10], tote;
inline void addEdge(int u, int v) {
  e[++tote] = {v, head[u]};
  head[u] = tote;
}

int n, a[N + 10], b[N + 10], ans[N + 10];
int f[N + 10], cnte[N + 10], cntv[N + 10], res;
int hst[N + 10], toth;

int getrt(int x) {
  return f[x] == x ? x : getrt(f[x]);
}

inline int siz(int u) { return min(cntv[u], cnte[u]); }

void merge(int u, int v) {
  if (getrt(u) == getrt(v)) {
    u = getrt(u);
    res -= siz(u);
    cnte[u]++;
    res += siz(u);
    hst[++toth] = u;
  } else {
    u = getrt(u), v = getrt(v);
    if (cntv[u] < cntv[v]) swap(u, v);
    res -= siz(u) + siz(v);
    cntv[u] += cntv[v];
    cnte[u] += cnte[v];
    cnte[u]++;
    f[v] = u;
    res += siz(u);
    hst[++toth] = v;
  }
}

void undo() {
  int u = hst[toth];
  hst[toth] = 0; toth--;
  if (u == getrt(u)) {
    res -= siz(u);
    cnte[u]--;
    res += siz(u);
  } else {
    int v = f[u];
    res -= siz(v);
    cntv[v] -= cntv[u];
    cnte[v] -= cnte[u];
    cnte[v]--;
    f[u] = u;
    res += siz(u) + siz(v);
  }
}

void dfs(int u, int fa) {
  merge(a[u], b[u]);
  ans[u] = res;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == fa) continue;
    dfs(v, u);
  }
  undo();
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%d%d", a + i, b + i);
  for (int i = 1; i < n; i++) {
    int u, v; scanf("%d%d", &u, &v);
    addEdge(u, v), addEdge(v, u);
  }
  for (int i = 1; i <= n; i++) f[i] = i, cntv[i] = 1;
  dfs(1, 0);
  for (int i = 2; i <= n; i++)
    printf("%d%c", ans[i], " \n"[i == n]);
  return 0;
}