首页 > 代码库 > Codeforces Round #428C
Codeforces Round #428C
Journey
题意:给一颗树,边权都为1,从1出发,求走到叶子节点的边权和的期望(每次往孩子遍历的等概率的)
思路:从1出发dfs,每个点到下一个点的概率是当前节点的概率乘孩子节点的个数,也就是当前点的边数-1,到叶子节点后计算概率乘边权和然后相加就是了,1节点需要特殊处理一下
AC代码:
#include "iostream" #include "iomanip" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #pragma comment(linker, "/STACK:102400000,102400000") #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a,x) memset(a,x,sizeof(a)) #define step(x) fixed<< setprecision(x)<< #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define ll long long #define endl ("\n") #define ft first #define sd second #define lrt (rt<<1) #define rrt (rt<<1|1) using namespace std; const long long INF = 1e18+1LL; const int inf = 1e9+1e8; const int N=1e5+100; const ll mod=1e9+7; vector<int> vex[N]; double dfs(int u, int fa, int l, double p){ if(vex[u].size()==1){//cout<<p*l<<endl; return p*l; } double ret=0.0; for(auto v : vex[u]){ //cout<<u<<" "<<vex[u].size()<<endl; if(v!=fa) ret+=dfs(v,u,l+1,p/(vex[u].size()-1 )); } return ret; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n; cin>>n; for(int i=1; i<n; ++i){ int u,v; cin>>u>>v; vex[u].pb(v), vex[v].pb(u); } vex[1].pb(0); double ans=dfs(1,0,0,1.0); cout<<step(6)ans<<endl; return 0; }
Codeforces Round #428C
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。