The 2023 ICPC Asia Regionals Online Contest (1)，不要选时光机，用签到送的金币就可以练习

G Spanning Tree

题意

起初树只有n个节点，没有边，按照如下操作进行n-1次，
对于第i次操作，选择$a_i,b_i$ ,从$a_i$ 所在的块中随机选出一个节点$u_i$，从$b_i$ 所在的块中随机选出一个节点$v_i$， 连接$u_i,v_i$
保证最终会形成一个树，求构造出的这个树和给出的标准的树T能够完全相同的期望（对 998244353取模）

保证第$i$次操作前,$a_i,b_i$ 不在同一个块。

定义一个节点v所在的块即v能到达的所有节点的集合（包括v本身）

请注意，所求的期望可能是0。

思路

可以得出，最终期望一定是0或者 $\frac{1}{s}$ ： 每次连接两个块时，最多只有一种连接方式能够使得所连边的情况和最终的树匹配。而本次操作会使得操作前的期望$s_{i-1}$ 再乘上 $\frac{1}{sz_a*sz_b}$ ($sz_a,sz_b$表示a和b当前所在块的节点数量)。 因此最终的期望的分子一定是1。（由于期望是一个分数，所以最总答案为分母s在MOD的模域下的逆元$inv(s)$)

本体涉及到区块的合并，于是很容易想到并查集，利用并查集便能轻松求出期望。但本体的难点不在于算出期望，而是判断何时应该输出0。

下面思考何时期望为0。

显而易见，每次操作时，a所在的块和b所在的块都是最终树T树上的某个子树的一部分。因此这两个块都会有自己的“根”，而如果我们要合并这两个子树， 就一定是将一个子树的根作为另一个子树的某个节点的儿子。假设我们要将a所在子树的根 $find(a)$ 拼接在b块的某个节点上，那么$find(a)$的父节点就一定和b在同一个块。我们可以通过$find(x) == find(y)$ 来判断某两个节点是否是在同一个块上，使用$father[x]$来表示x节点在T树上对应的父节点。
因此能够找到一条正确的边就等价于 $find(father[find(a)]) == find(b) || find(father[find(b)]) == find(a)$，如果该条件不成立，那么就代表无法构建合适的边，就应该打印0并退出程序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<vector>
using namespace std;
const int N = 1e6+5;
int pre[N];//并查集中的父节点
int father[N];// 最终树中某个节点的父节点
typedef long long LL;
const int MOD = 998244353;
pair<int,int> ope[N];//n-1次操作
vector<int> vec[N];//存储边的关系
int sz[N];//在每次合并时，sz[i]表示目前以i为根的块的数量s

int find(int x){//并查集的找根操作
    if(pre[x] == x) return x;
    else return pre[x] = find(pre[x]);
}
void join(int x,int y){//并查集的合并操作
    int fx = find(x),fy = find(y);
    if(fx != fy){
        sz[fy] = sz[fx] + sz[fy];
        pre[fx] = fy;
    }
    return;
}
LL qp(LL a , LL b){//quick pow 快速幂
    LL ans = 1ll;
    while(b){
        if(b & 1){
            ans = ans * a % MOD;
        }
        a = a * a % MOD;
        b >>=1;
    }
    return ans;
}
LL inv(LL x){//求逆元
    return qp(x,MOD-2);
}
//dfs来判断T树中的父亲关系
bool isgone[N];
void dfs(int x){
    for(int p : vec[x]){
        if(!isgone[p]) {
            isgone[p] = true;
            father[p] = x;
            dfs(p);
        }
    }
    return;
}
int main(){
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++) pre[i] = i;
    for(int i = 1;i<=n;i++) sz[i] = 1;
    int l , r;
    for(int i = 1;i<n;i++){
        scanf("%d %d",&l,&r);
        ope[i] = {l,r};
    }
    int u , v;
    for(int i = 1;i<n;i++){
        scanf("%d %d",&u,&v);
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    isgone[1] = true;
    dfs(1);//令T变为以1为根节点的树
    long long sum = 1ll;
    for(int i = 1;i<n;i++){
        int a = ope[i].first;
        int b = ope[i].second;
        if(find(father[find(a)]) == find(b)){
            sum = sum *sz[find(a)] % MOD * sz[find(b)] % MOD;
            join(a,b);
        }else if(find(father[find(b)]) == find(a)){
            sum = sum *sz[find(a)] % MOD * sz[find(b)] % MOD;
            join(b,a);
        }else{
            // cout<<a<<" "<<b<<endl;
            cout<<0;
            return 0; 
        }
    }
    // cout<<sum<<endl;
    cout<<inv(sum);

    return 0;
}