题解：每次有两个事件：
- y
y去挑战xx，如果赢了可以坐在x
- x的位置，打平或者输了就要被淘汰。
- 询问在进行所有一类事件后，有多少种情况可以让x
- x现在还没有被淘汰。
对于第二类事件，我们假设x
x挑战了别人aa次，被挑战了bb次，那他没有被淘汰的概率就是3n⋅(133n⋅(31)a⋅(32)b。因此我们只要知道a,ba,b的值就可以知道答案。因此我们需要维护a,ba,b的值。对于第一类事件，我们画画图就会发现它会形成树状关系。那么我们就可以维护这颗树的节点信息，然后去询问就好了。很容易想到并查集了，但是这里似乎并不能直接用路径压缩，原因听一位巨巨说因为每个节点都有权值，根节点也有权值，每次查询的时候会重复累加根节点的信息，所以需要按秩合并。我们可以维护两个信息：每个人的总比赛场次，主场比赛场次。对于yy挑战xx，那么肯定y,xy,x的总比赛场次都加11，xx主场比赛场次加11。那么，对于集合yy合并到集合xx，会将xx设为yy的父亲，因为每个节点都包含着它当前这个集合的增量信息，也就意味着集合yy里的增量会凭空多增加xx的增量。因此合并的时候需要减去。然后findfind的时候累加增量即可。
这个题从概率的方向去考虑方案数
用并查集来维护之间的战斗关系，同时记录客场作战次数和主场作战次数
两个集合合并的的时候要减去fa的信息，
1 #include<bits/stdc++.h>
2 typedef long long LL;
3 using namespace std;
4 const int N = 2E5+10, mod = 998244353;
5 LL w[N],v[N],rk[N],f[N];
6 struct node
7 {
8 int fa;
9 LL _w,_v;
10 };
11 LL _pow(LL a,LL n)
12 {
13 LL ret = 1;
14 while(n)
15 {
16 if(n & 1) ret = a * ret % mod;
17 a = a * a % mod;
18 n >>= 1;
19 }
20 return ret;
21 }
22 LL Inv(LL n)
23 {
24 return _pow(n, mod - 2);
25 }
26 node _find(int x)
27 {
28 if(x == f[x]) return node{x,w[x],v[x]};
29 node t = _find(f[x]);
30 return node{t.fa, t._w + w[x], t._v + v[x]};
31 }
32 void _merge(int x,int y)
33 {
34 int t1 = _find(x).fa;
35 int t2 = _find(y).fa;
36 if(t1 != t2)
37 {
38 w[t1]++;
39 v[t1]++;
40 w[t2]++;
41 if(rk[t1] >= rk[t2])
42 {
43 w[t2] -= w[t1];
44 v[t2] -= v[t1];
45 f[t2] = t1;
46 rk[t1]++;
47 }
48 else
49 {
50 w[t1] -= w[t2];
51 v[t1] -= v[t2];
52 f[t1] = t2;
53 rk[t2]++;
54 }
55 }
56 }
57 int main()
58 {
59
60 for(int i = 0; i < N; ++i)
61 {
62 f[i] = i;
63 }
64 int n,m,c,x,y;
65 cin >> n >> m;
66 LL t = _pow(3,n);
67 for(int i = 0; i < m; ++i)
68 {
69 scanf("%d",&c);
70 if(c == 1)
71 {
72 scanf("%d %d",&x,&y);
73 _merge(x,y);
74 }
75 else
76 {
77 scanf("%d",&x);
78 node t1 = _find(x);
79 LL a = t1._v, b = t1._w - t1._v;
80 LL ans = t * Inv(_pow(3,b)) % mod * _pow(2,a) % mod * Inv(_pow(3,a)) % mod;
81 printf("%lld
",ans);
82 }
83 }
84 return 0;
85 }