标签归档：计蒜客

计蒜客 Random Access Iterator

发表评论

原题链接：https://nanti.jisuanke.com/t/41392
竟然做出来一道这么复杂的概率+DFS+逆元题，开心到爆炸，特此发题解一篇^v^

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#define MOD 1000000007
#define ll long long
using namespace std;
int n;
int MDep;
vector<int> edges[1000005];
bool visited[1000005];
ll quickpow(ll a, ll b) {
    if (b == 0)return 1;
    ll re = quickpow(a, b / 2) % MOD;
    re = (re * re) % MOD;
    if (b % 2 == 1)re *= a % MOD;
    return re % MOD;
}
inline ll inv(ll x) {
    return quickpow(x, MOD - 2) % MOD;
}
inline ll chance1(ll TotNode) {
    ll ch = (inv(TotNode)) % MOD;
    return ch;
}
inline ll chance2(ll onceCh,ll TotNode) {
    ll onceNonch = (1ll-onceCh+MOD) % MOD;
    ll nonch = quickpow(onceNonch, TotNode);
    ll fin = (1ll - nonch + MOD) % MOD;
    return fin;
}
int dfsMaxDep(int node) {
    int maxDep = 1;
    bool hasChild = false;
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (visited[edges[node][i]])continue;
        hasChild = true;
        maxDep = max(maxDep, dfsMaxDep(edges[node][i]) + 1);
    }
    return maxDep;
}
ll dfsChance(int depth,int node){
    if (depth == MDep)return 1;
    ll ch = 0,sCh=chance1(node==1?edges[node].size(): edges[node].size()-1);
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (visited[edges[node][i]])continue;
        ll CurCH = dfsChance(depth + 1, edges[node][i]);
        if (CurCH) {
            ch += (CurCH * sCh) % MOD;
            ch %= MOD;
        }
    }
    return chance2(ch, node == 1 ? edges[node].size() : edges[node].size() - 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    MDep = dfsMaxDep(1);
    memset(visited, false, sizeof(visited));
    ll ch = dfsChance(1, 1);
    cout << ch;
}