如何将Random Access Iterator改写为一个长尾词的？
- 内容介绍
- 文章标签
- 相关推荐
本文共计749个文字，预计阅读时间需要3分钟。
最近，Kumiko开始学习在C++标准模板库中使用容器。她非常喜欢使用`std::vector`。对于她来说，这个容器像普通数组一样方便操作。然而，她对随机访问功能有所顾虑。
Recently Kumiko learns to use containers in C++ standard template library.
She likes to use thestd::vectorvery 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 thestd::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 ofnnvertices, and11is 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 functiondfs(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 modulo10^9 + 7109+7.
Input
The first line contains an integernn- the number of vertices in the tree(2 \le n \le 10^6)(2≤n≤106).
Each of the nextn - 1n−1lines describes an edge of the tree. Edgeiiis denoted by two integersu_iui?andv_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.
样例输入
5 1 2 1 3 3 4 3 5
样例输出
750000006
样例解释
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)%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 = %d\n",max_depth); solve(1, 1); printf("%lld", dp[1]); return 0; }
本文共计749个文字，预计阅读时间需要3分钟。
最近，Kumiko开始学习在C++标准模板库中使用容器。她非常喜欢使用`std::vector`。对于她来说，这个容器像普通数组一样方便操作。然而，她对随机访问功能有所顾虑。
Recently Kumiko learns to use containers in C++ standard template library.
She likes to use thestd::vectorvery 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 thestd::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 ofnnvertices, and11is 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 functiondfs(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 modulo10^9 + 7109+7.
Input
The first line contains an integernn- the number of vertices in the tree(2 \le n \le 10^6)(2≤n≤106).
Each of the nextn - 1n−1lines describes an edge of the tree. Edgeiiis denoted by two integersu_iui?andv_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.
样例输入
5 1 2 1 3 3 4 3 5
样例输出
750000006
样例解释
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)%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 = %d\n",max_depth); solve(1, 1); printf("%lld", dp[1]); return 0; }