石头剪刀布（2019Wannafly winter camp day3 i）带权并查集+按秩合并好题

思路：　

按照题意描述，所有y挑战x的关系最后会形成一棵树的结构，n个人的总方案数是 3ⁿ种，假设一个人被挑战（主场作战）a次，挑战别人（客场）b次，那么这个人存活到最后的方案数就是3ⁿ*（2/3）^a*(1/3)^b

也就是我们知道这个a和b就可以得到答案了，那要怎么维护呢。

这里用到并查集（jls niub！）

我们用w表示一个节点总共比赛的场次数，v表示主场作战的场次数，如果我们现在把y这个集合并向x这个集合（y挑战x），那么对于XW和Xv肯定都加一，而Yw也加一，如果我们接下来能很好的合并这些信息，那我们就AC了。

这里想了很久，才想明白要怎么做。我们先考虑暴力一点的并查集，就是不路径压缩，那每个节点就可以向上把所有父节点的信息全部加起来，就是我们最后要的某一个节点的W和V了，但是这样做会TLE，因为我们没有路径压缩，查找的时间复杂度很可能退化成O（n）,但是我们又不能路径压缩（为什么不行，大家可以尝试一下，反正我自闭了一下午加一晚上）。

普通的带权并查集我们用的都是路径压缩版本的，而这里我们要按秩合并，这样查找的时间复杂度就可以被优化到O（logn）。

曾经我一直以为带权并查集的路径压缩和按秩合并是同一个东西，这道题真的学到了。。

#include<bits/stdc++.h>

#define CLR(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const int maxn=;

int fa[maxn],Rank[maxn];

ll w[maxn],v[maxn];

int n,m;

int op,x,y;

ll p= ;

struct node{

    int fx;

    ll w,v;

};

ll qpow(ll a,ll b){

    a%=p;

    ll res=;

    while(b>)

    {

        if(b&){

            res*=a;

            res%=p;

        }

        b>>=;

        a=a*a%p;

    }

    return res;

}

void init(){

    for(int i=;i<=n;i++){

        fa[i]=i;

        w[i]=;

        v[i]=;

        Rank[i]=;

    }

}

node find(int x){

    if(x==fa[x]) return {fa[x],w[x],v[x]};

    int tep=fa[x];

    node e;

    e.w=w[x],e.v=v[x];

    while(tep!=fa[tep]){

        e.w+=w[tep],e.v+=v[tep];

        tep=fa[tep];

    }

    e.fx=tep;

    e.v+=v[tep],e.w+=w[tep];

    return e;

}

void baba(int x,int y){

    node ex=find(x),ey=find(y);

    if(ex.fx!=ey.fx){

        w[ex.fx]+=;

        v[ex.fx]+=;

        w[ey.fx]+=;

        v[ey.fx]+=;

        if(Rank[ex.fx]>=Rank[ey.fx])

        {

            w[ey.fx]-=w[ex.fx];

            v[ey.fx]-=v[ex.fx];

            fa[ey.fx]=ex.fx;

            Rank[ex.fx]++;

        }else{

            w[ex.fx]-=w[ey.fx];

            v[ex.fx]-=v[ey.fx];

            fa[ex.fx]=ey.fx;

            Rank[ey.fx]++;

        }

    }

}

int main(){

    while(cin>>n>>m)

    {

        init();

        ll res=qpow(,n);

        ll ans;

        while(m--)

        {

            scanf("%d%d",&op,&x);

            if(op==){

                scanf("%d",&y);

                baba(x,y);

            }else{

                node ex=find(x);

                ll a=ex.v;

                ll b=ex.w-ex.v;

                ans=res*qpow(qpow(,b),p-)%p*qpow(,a)%p*qpow(qpow(, a),p-)%p;

                printf("%lld\n",ans);

            }

        }

    }

}

题目描述

可怜去观看了石头剪刀布的世界最高赛事 WRSP。

今年的比赛一共有 n 名选手参加，在比赛开始时，每名选手都会收到一张卡片，这张卡片上写着剪刀、石头、布中的一个。显然初始的卡牌分配情况有 3^n种。

比赛场地一共有 n 个座位，最开始第 ii 个选手坐在第 i 个座位上。

接下来发生了 m 个事件，事件有两种：

1 x y，主办方撤去了第 yy 个座位，原来在第 yy 个座位上的选手 bb 需要和 xx 个座位上的选手 aa 利用他们的卡片进行一场石头剪刀布比赛，如果 bb 赢了 aa，则选手 aa 被淘汰，选手 bb 坐到第 x 个座位上；否则（打平或者 bb 输了），则选手 bb 被淘汰，选手 aa 的坐位不变。
2 x，可怜提出了一个问题，她想要知道在进行了之前的所有第 1 类事件后，有多少种卡牌分配情况可以让第 x 个选手到现在还没有被淘汰。

输入描述

第一行输入两个整数 n,m(1 \leq n,m \leq 2 \times 10^5)n,m(1≤n,m≤2×105)，表示选手个数和事件个数。

接下来 mm 行，每行描述了一个事件。如果是第一类事件，则输入三个整数 1\ x\ y(1 \leq x,y \leq n, x \neq y)1 x y(1≤x,y≤n,x̸=y) 且这两个座位在之前没有被撤去；如果是第二类事件，则输入两个整数 2\ x(1 \leq x \leq n)2 x(1≤x≤n)。

输出描述

对于每个第二类事件，输出一行一个整数，表示这个选手还没有被淘汰的分配情况个数对 998244353998244353 取模后的值。

样例输入 1

样例输出 1

石头剪刀布（2019Wannafly winter camp day3 i） 带权并查集+按秩合并 好题

石头剪刀布（2019Wannafly winter camp day3 i）带权并查集+按秩合并好题