2019. Net race J.Random Access Iterator (probability)

Topic link: https://nanti.jisuanke.com/t/41392

Main idea of the title:

Give you a tree, if you are in node u, the number of sub-nodes is son, then you have the chance to select one sub-node to search downward each time. This operation will search for the deepest degree, but not necessarily correct. What is the probability that you can find the deepest degree is the depth of the tree?

Train of thought:

Considering that it is easy to be self-closing, it is certainly not possible to calculate k choices for each node. So we think backwards. dp[u] means that the search starts from the U node, and can not find the deepest probability. Then things become simpler. The transfer equation is

It means that I chose son times, and I can't search for the deepest depth, so I don't have to think about searching several times to find the deepest depth.

The final answer is 1-dp[1]

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=1e6+10;
vector<int>G[maxn];
const int mod=1e9+7;
//Extend GCD
int ex_gcd(int a,int b,int &x,int &y){
   if(b==0){x = 1;y = 0;return a;}
   int g = ex_gcd(b,a%b,x,y);
   int temp = x;
   x = y;
   y = temp - a/b*y;
   return g;
}
//Another way of writing extended Euclid
void ex_gcd(int a,int b,int &d,int &x,int &y){
    //A Set of Solutions for ax+by=gcd(a,b)
    if(!b){
        d=a,x=1,y=0;
    }
    else{
        ex_gcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}

//Inverse element
int inv(int a,int mod){
   int X,Y;
   int g = ex_gcd(a,mod,X,Y);
   if(g!=1)return -1;
   return (X%mod + mod)%mod;
}
int dp[maxn];
int n;
int depth[maxn];
int maxdep;
int pow_mod(int a,int n,int mod){
    if(n==0)return 1;
    int ans=pow_mod(a,n/2,mod);
    ans=ans*ans%mod;
    if(n%2==1)ans=ans*a%mod;
    return ans;
}

void dfs1(int u,int fa){
    depth[u]=depth[fa]+1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==fa)continue;
        dfs1(v,u);
    }
}
void dfs(int u,int fa){
    if(G[u].size()==1&&u!=1){
        if(depth[u]==maxdep){
            dp[u]=0;
        }
        else{
            dp[u]=1;
        }
        return;
    }
    int sz=0;
    dp[u]=0;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==fa)continue;
        sz++;
        dfs(v,u);
        dp[u]+=dp[v];
        dp[u]%=mod;
    }
    dp[u]=inv(sz,mod)*dp[u]%mod;
    dp[u]=pow_mod(dp[u],sz,mod);
    //printf("debug %lld\n",dp[u]);
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%lld%lld",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    depth[0]=0;
    dfs1(1,-1);
    maxdep=0;
    for(int i=1;i<=n;i++){
        maxdep=max(maxdep,depth[i]);
    }
    dfs(1,0);
    printf("%lld\n",(1+mod-dp[1])%mod);
    return 0;
}

/*
7
1 2
1 3
2 4
2 5
3 6
3 7


3
1 2
2 3
*/

 

Posted on Tue, 08 Oct 2019 10:35:45 -0700 by s0me0ne