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;
}

標籤：其他

上一篇：gitlab ci 集成 eslint/prettier/tsc 做代碼審查，并使用 eslint 輸出作為顯示代碼質量

下一篇：返回列表