Random Access Iterator-白红宇

Random Access Iterator

阅读量：4477 次

发布时间：2019-06-08

本文共 2497 字，大约阅读时间需要 8 分钟。

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 $\le n \le 10^6)(2≤n≤106).$

Each of the next $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.

样例输入复制

51 21 33 43 5

样例输出复制

750000006

样例解释

Kumiko's code has $\frac{3}{4}43 probability to output the correct answer.$

#include 
        
         using namespace std;typedef long long ll;const int maxn = 3e6 + 10;const ll mod=1e9+7;int n;vector
         
           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

转载于:https://www.cnblogs.com/czy-power/p/11482677.html

你可能感兴趣的文章

【原创】StreamInsight查询系列（七）——基本查询操作之基础排序