原题链接: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; } |