Random Access Iterator

发布时间：2020-12-16 09:17:09 所属栏目：百科来源：网络整理

导读：Recently Kumiko learns to use containers in C++ standard template library. She likes to use the?std::vector?very much. It is very convenient for her to do operations like an ordinary array. However,she is concerned about the random-access

Recently Kumiko learns to use containers in C++ standard template library.

She likes to use the?std::vector?very much. It is very convenient for her to do operations like an ordinary array. However,she is concerned about the random-access iterator use in the?std::vector. She misunderstanding its meaning as that a vector will return an element with equal probability in this container when she access some element in it.

As a result,she failed to solve the following problem. Can you help her?

You are given a tree consisting of?

The height of a tree is defined as the maximum number of vertices on a path from the root to a leaf.

Kumiko‘s code is like the following pseudo code.

She calls this function?dfs(1,1),and outputs the maximum value of depth array.

Obviously,her answer is not necessarily correct. Now,she hopes you analyze the result of her code.

Specifically,you need to tell Kumiko the probability that her code outputs the correct result.

To avoid precision problem,you need to output the answer modulo? $10^9 + 7109+7.$

Input

The first line contains an integer? $10^6)(2≤n≤106).$

Each of the next? $integers?u_iui??and?v_ivi?,the indices of vertices it connects?(1 le u_i,v_i le n,u_i cancel= v_i)(1≤ui?,vi?≤n,ui?=?vi?).$

It is guaranteed that the given edges form a tree.

Output

Print one integer denotes the answer.

样例输入

样例输出

750000006

样例解释

Kumiko‘s code has? $frac{3}{4}$

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 3e6 + 10;
const ll mod=1e9+7;

int n;
vector<int> e[maxn];
int dep[maxn],max_depth;
ll dp[maxn];

inline void init(int cur,int fa) {
    for (register int i = 0; i < e[cur].size(); ++i) {
        int to = e[cur][i];
        if(to==fa)continue;
        dep[to] = dep[cur] + 1;
        max_depth = max(max_depth,dep[to]);
        init(to,cur);
    }
}

inline ll fast_pow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}

inline void solve(int cur,int fa) {
    bool flag = false;
    int tot=e[cur].size();
    if(cur!=1)--tot;
    int probability=fast_pow(tot,mod-2);
    int sum=0;
    for(register int i=0;i<e[cur].size();++i){
        int to=e[cur][i];
        if(to==fa)continue;
        solve(to,cur);
        sum=(sum+(1-dp[to]+mod)%mod*probability%mod)%mod;
        flag=true;
    }
    if(flag){
        dp[cur]=(1-fast_pow(sum,tot)+mod)%mod;
    }
    else{
        if(dep[cur]==max_depth) {
            dp[cur] = 1;
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.txt","r",stdin);
#endif
    scanf("%d",&n);
    for (register int i = 1,u,v; i < n; ++i) {
        scanf("%d%d",&u,&v);
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    init(1,1);
    //printf("debug max_depth = %dn",max_depth);
    solve(1,1);
    printf("%lld",dp[1]);
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!