[2019徐州网络赛J题]Random Access Iterator

题目链接

大致题意：从根节点出发，在节点x有son[x]次等概率进入儿子节点，求到达最深深度的概率。son[x]为x节点的儿子节点个数。

又又又又没做出来，心态崩了。

下来看了官方题解后发觉自己大体思路是没错的，但是细节太弱了Orz。

大体思路：设dp[x]为以x为根节点，求到达最深深度的概率。先跑一遍dfs，求出每个点的子节点数，每个点的深度以及最深深度。

我们可以求得从x点一次不能到达最深深度的概率为$cnt =1-(\tfrac{\sum_{y\epsilon x } dp[y]}{son[x]})$

则$dp[x]=1-cnt^{son[x]}$为son[x]次能到达最深深度的概率。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 2e6 + ;

 const ll mod = 1e9 + ;

 struct node {

     int s, e, next;

 }edge[maxn];

 int head[maxn], len;

 void init() {

     memset(head, -, sizeof(head));

     len = ;

 }

 void add(int s, int e) {

     edge[len].e = e;

     edge[len].next = head[s];

     head[s] = len++;

 }

 int mxd[maxn], d[maxn], son[maxn];

 ll dp[maxn];

 ll qpow(ll a, ll b, ll mod) {

     ll ans = ;

     while (b) {

         if (b & )ans = ans * a % mod;

         a = a * a % mod;

         b >>= ;

     }

     return ans;

 }

 void dfs(int x, int fa) {

     mxd[x] = d[x];

     for (int i = head[x]; i != -; i = edge[i].next) {

         int y = edge[i].e;

         if (y == fa)continue;

         d[y] = d[x] + ;

         son[x]++;

         dfs(y, x);

         mxd[x] = max(mxd[x], mxd[y]);

     }

 }

 void dfs1(int x, int fa) {

     ll sum = ;

     for (int i = head[x]; i != -; i = edge[i].next) {

         int y = edge[i].e;

         if (y == fa)continue;

         if (mxd[y] == mxd[]) {

             dfs1(y, x);

             sum = (sum + dp[y]) % mod;

         }

     }

     if (son[x] == )

         dp[x] = ;

     else {

         ll p = sum * qpow(son[x], mod - , mod) % mod;

         p = ( - p + mod) % mod;

         dp[x] = ( - qpow(p, son[x], mod) + mod) % mod;

     }

 }

 int main() {

     int n;

     scanf("%d", &n);

     init();

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

         int x, y;

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

         add(x, y), add(y, x);

     }

     dfs(, );

     dfs1(, );

     printf("%lld\n", dp[]);

 }

[2019徐州网络赛J题]Random Access Iterator的相关教程结束。