大佬教程收集整理的这篇文章主要介绍了Random Access Iterator，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
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 nn vertices,and 11 is the root of this tree. You are asked to calculate the height of it.
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.
The first line contains an Integer nn - the number of vertices in the tree (2 \le n \le 10^6)(2@H_502_115@≤n@H_502_115@≤106).
Each of the next n - 1n−1 lines describes an edge of the tree. Edge ii is denoted by two 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@H_502_115@≤ui?,vi?@H_502_115@≤n,ui?@H_502_115@=?vi?).
it is guaranteed that the given edges form a tree.
Print one Integer denotes the answer.
5 1 2 1 3 3 4 3 5
Kumiko‘s code has \frac{3}{4}43? probability to output the correct answer.
#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)%@H_637_517@mod; a=(a*a)%@H_637_517@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)%@H_637_517@mod; flag=true; } if(flag){ dp[cur]=(1-fast_pow(sum,tot)+mod)%@H_637_517@mod; } else{ if(dep[cur]==@H_637_517@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 = %d\n",max_depth); solve(1,1); printf("%lld",dp[1]); return 0; }
以上是大佬教程为你收集整理的Random Access Iterator全部内容，希望文章能够帮你解决Random Access Iterator所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。