AtCoder Beginner Contest 302 H. Ball Collector 题解 可撤销并查集

这篇具有很好参考价值的文章主要介绍了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)\)文章来源地址https://www.toymoban.com/news/detail-458407.html

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

到了这里,关于AtCoder Beginner Contest 302 H. Ball Collector 题解 可撤销并查集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • AtCoder Beginner Contest 336 C - Even Digits题解

    Time Limit: 2 sec / Memory Limit: 1024 MB Score: 300300 points Problem Statement A non-negative integer �n is called a  good integer  when it satisfies the following condition: All digits in the decimal notation of �n are even numbers (00, 22, 44, 66, and 88). For example, 00, 6868, and 20242024 are good integers. You are given an integer 

    2024年01月20日
    浏览(48)
  • Atcoder Beginner Contest 324 G Generate Arrays 题解-Treap

    为了更好的阅读体验,请点击这里 题目链接 套上平衡树板子就能做的很快的题,然后因为是指针存树,因此交换只需要把序列大小较小的挨个拿出来插到相应的地方即可。复杂度 (O(N log^2 N)) 。 但是一定要记住 不可以直接使用 std::swap 交换包含带有指针的类的实例(如代码

    2024年02月08日
    浏览(41)
  • Atcoder Beginner Contest 324 F Beautiful Path 题解-分数规划

    为了更好的阅读体验,请点击这里 分数规划小技巧: 尽可能将式子写成存在某种取值,使得不等式成立的形式。 不然可能需要绕几个弯才能想出来。 题目链接 题目大意:给出一个 DAG,每条边有一个 (b_i, c_i) ,保证从编号小的边向编号大的边连边,且 (1) 到 (n) 必有路径

    2024年02月08日
    浏览(36)
  • Atcoder beginner contest 336 -- E -- Digit Sum Divisible --- 题解(数位dp)

    目录   E -- Digit Sum Divisibl 题目大意: 思路解析: 代码实现: 给你一个整数n,让你找出小于等于n的数中一共有多少个好整数,并输出好整数的个数。对好整数的个数定义为如果一个数能被他的数位之和整除,则称这个数为好整数。例如 12 能被 3 整除。 n=10^14。 看到数位之和

    2024年01月16日
    浏览(52)
  • Atcoder Beginner Contest 321 G - Electric Circuit 题解 - 状压dp | 指定最低位

    为了更好的阅读体验,请点击这里 题目链接:G - Electric Circuit 看到了 (N) 的数据范围,因此是显然的状压 dp。 不妨设 (f_S) 为仅使用 (S) 集合中的所有点,能够连成恰好 (1) 个连通块的方案数。 (g_S) 为仅使用 (S) 集合中的所有点的方案数,其中 (cntr(S)) 在 (S) 中为

    2024年02月05日
    浏览(51)
  • AtCoder Beginner Contest 334

    给定两个数 (b,g(b neq g)) ,如果 (b) 大则输出 Bat ,否则输出 Glove 。 比较大小输出即可。 神奇的代码 给定 (a,m,l,r) ,问有多少个整数 (k) 满足 (l leq a + mk leq r) . 对不等式化简一下即为 (frac{l - a}{m} leq k leq frac{r - a}{m}) 的整数个数。 答案就是 (lfloor frac{r - a}{m} r

    2024年02月04日
    浏览(33)
  • AtCoder Beginner Contest 305

    给定一个数字 (x) ,输出一个数字,它是最接近 (x) 的 (5) 的倍数。 令 (y = x % 5) ,如果 (y leq 2) ,那答案就是 (x - y) ,否则就是 (x + 5 - y) 。 神奇的代码 给定 (ABCDEFG) 的相邻距离,给定两个字母,问它们的距离。 累加距离即可。 神奇的代码 二维平面,有一个矩形

    2024年02月08日
    浏览(52)
  • AtCoder Beginner Contest 341

    给定 (n) ,输出 (n) 个 (0) 和 (n+1) 个 (1) 交替的字符串。 (101010...) 循环输出即可。 神奇的代码 货币兑换。 (A) 国货币每 (x_a) 钱可兑换 (B) 国货币 (y_a) 钱。 (B) 国货币每 (x_b) 钱可兑换 (C) 国货币 (y_b) 钱。 ... 给定你拥有的每国货币钱数和兑换规则,依次兑换

    2024年02月19日
    浏览(25)
  • AtCoder Beginner Contest 328

    给定 (n) 个数字和一个数 (x) 。 问不大于 (x) 的数的和。 按找要求累计符合条件的数的和即可。 神奇的代码 给定一年的月数和一个月的天数。 问有多少对 ((i,j)) ,表示第 (i) 个月的第 (j) 日, (i,j) 的数位上每个数字都是一样的。 范围只有 (O(100^2)) ,枚举所有的

    2024年02月05日
    浏览(34)
  • AtCoder Beginner Contest 330

    给定 (n) 个学生的分数,以及及格分 (x) ,问多少人及格了。 依次判断即可。 神奇的代码 回答 (n) 个问题,每个问题给定 (a,l,r) ,问函数 (f(x) = |x - a|) 在 ([l,r]) 的最小值。 全定义域下,最小值显然在 (x=a) 取得。绝对值函数图像是 (V) 型。 现在限定在 ([l,r]) ,则

    2024年02月05日
    浏览(115)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包