AtCoder Beginner Contest 302 H. Ball Collector 题解
AtCoder Beginner Contest 302 H. Ball Collector
题意跳过。
可以视作将 \(a_i, b_i\) 之间连了一条边，然后 \(a_i, b_i\) 之间只能选一个等价于对于一条边只能选择其一个端点。那么对于只包含树的联通块而言，如果都选择儿子节点，那么会有一个根节点无法被选择上；而对于包含至少一个环的联通块而言，所有节点都可以被选择上，例如，可以先找出环，然后利用环上的边将环上的点都选上，然后对于连上环的边，选上边另一头的节点即可，这样慢慢延申到整个联通块。
因此，答案为：所有节点个数 - 树联通块个数
于是问题就转化为如何维护树联通块个数了。
可以使用并查集维护每一个联通块内包含的边的个数，这样每一个联通块是否为树就很好判断了。如果这是一条链，那么并查集非常好操作，但是这是一棵树，于是需要回退操作。于是可以使用可撤销并查集来做。
由于路径压缩会破坏联通块的结构，因此可撤销并查集仅使用启发式合并/按秩合并的方式，具体为开一个栈记录每次更新时原来的信息，例如代码假设是把 \(u\) 节点合并进入 \(v\) 节点，那么要记录 \(u, v, pa_u\) 这三个值。时间复杂度与仅使用启发式合并时间复杂度相同：\(O(n \log n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
#define IL inline
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define dbg1(x) cout << #x << " = " << x << ", "
#define dbg2(x) cout << #x << " = " << x << endl
template<typename Tp> IL void read(Tp &x) {
x=0; int f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch == '-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
x *= f;
}
int buf[42];
template<typename Tp> IL void write(Tp x) {
int p = 0;
if(x < 0) { putchar('-'); x=-x;}
if(x == 0) { putchar('0'); return;}
while(x) {
buf[++p] = x % 10;
x /= 10;
}
for(int i=p;i;i--) putchar('0' + buf[i]);
}
const int N = 200000 + 5;
int n, tree_cnt = 0;
int a[N], b[N];
int pa[N], sz[N], cnt[N], col[N], ans[N];
stack<array<int, 3> > sta; // 假设上一次操作是 u -> v，那么 0 -> u, 1 -> v, 2 -> pa[u]
vector<int> G[N];
void solve() {
read(n);
for (int i = 0; i < n; i++) {
read(a[i]); a[i]--;
read(b[i]); b[i]--;
}
for (int i = 0; i < n - 1; i++) {
int u, v; read(u); read(v); u--; v--;
G[u].pb(v); G[v].pb(u);
}
fill(sz, sz + n, 1);
fill(cnt, cnt + n, 0);
iota(pa, pa + n, 0);
function < int(int) > findset = [&] (int u) {
return u == pa[u] ? u : findset(pa[u]);
};
auto merge = [&] (int u, int v) {
int fu = findset(u), fv = findset(v);
if (sz[fu] > sz[fv]) { swap(fu, fv); swap(u, v);}
sta.push({fu, fv, pa[fu]});
pa[fu] = fv; sz[fv] += sz[fu]; cnt[fv] += cnt[fu] + 1;
};
auto undo = [&] () {
auto now = sta.top(); sta.pop();
int fu = now[0], fv = now[1], pfu = now[2];
pa[fu] = pfu; sz[fv] -= sz[fu]; cnt[fv] -= cnt[fu] + 1;
};
tree_cnt = n;
function < void(int, int) > dfs = [&](int u, int fa) {
int fau = findset(a[u]), fbu = findset(b[u]);
if (fau == fbu) {
if ((cnt[fau]++) == sz[fau] - 1) {
tree_cnt --;
}
}
else {
if (sz[fau] == cnt[fau] + 1 || sz[fbu] == cnt[fbu] + 1) tree_cnt --;
merge(a[u], b[u]);
}
ans[u] = n - tree_cnt;
for (int v : G[u]) {
if (v == fa) continue;
dfs(v, u);
}
if (fau != fbu) {
undo();
if (sz[fau] == cnt[fau] + 1 || sz[fbu] == cnt[fbu] + 1) tree_cnt++;
}
else if ((--cnt[fau]) == sz[fau] - 1) {
tree_cnt ++;
}
};
dfs(0, -1);
for (int i = 1; i < n; i++) {
write(ans[i]); putchar(" \n"[i == n - 1]);
}
}
int main() {
#ifdef LOCAL
freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
#endif
int T = 1;
// read(T);
while(T--) solve();
return 0;
}