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;
}
- 题解 Collector Beginner AtCoder Contestcollector beginner atcoder contest 题解collector beginner atcoder 题解beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328