Submission #1213683

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <iostream>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
vector<int> G[150001];
double dp[150001];
bool used[150001];
double res[150001];

double func(int v){
	used[v]=true;
	double res=0.0;
	int cnt=0;
	for(int i=0;i<G[v].size();i++){
		if(!used[G[v][i]]){
			res+=func(G[v][i]);
			cnt++;
		}
	}
	if(cnt==0){
		dp[v]=0.0;
		return (dp[v]+1.0);
	}
	dp[v]=(double)res/cnt;
	return (dp[v]+1.0);
}

void solve(int v,int p,double val){
	used[v]=true;
	if(p==-1){
		res[v]=val;
	}else{
		double pn=(double)G[v].size()-1.0;
		double nn=(double)G[v].size();
		if(pn==0){
			res[v]=dp[v];
			res[v]+=val;
		}else{
			res[v]=(dp[v]*pn/nn);
			res[v]+=val/nn;
		}
	}
	//printf("%d %d %.9f\n",v,p,val);
	val=res[v];
	//printf("%d %d %.9f\n",v,p,val);
	for(int i=0;i<G[v].size();i++){
		if(!used[G[v][i]]){
			int nv=G[v][i];
			double sendval=val;
			//printf("%.9f\n",sendval);
			if(p==-1){
				if(G[v].size()==1)sendval-=(dp[nv]+1.0);
				else{
					sendval-=(dp[nv]+1.0)/G[v].size();
					sendval*=(double)G[v].size()/(G[v].size()-1);
				}
			}else{
				if(G[v].size()==1)sendval-=(dp[nv]+1.0);
				else{
					//printf("sv %d %d %.9f\n",v,nv,sendval);
					sendval-=(dp[nv]+1.0)/((double)G[v].size());
					//printf("sv %d %d %.9f\n",v,nv,sendval);
					sendval*=(double)G[v].size()/(G[v].size()-1);
				}
			}
			solve(G[v][i],v,sendval+1.0);
		}
	}
	return;
}

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		int f,t;
		scanf("%d%d",&f,&t);
		f--;
		t--;
		G[f].push_back(t);
		G[t].push_back(f);
	}
	memset(used,false,sizeof(used));
	func(0);
	memset(used,false,sizeof(used));
	solve(0,-1,dp[0]);
	for(int i=0;i<n;i++){
		printf("%.9f\n",res[i]);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:90:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&f,&t);
                      ^

Judge Result