Submission #1570232


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> G[150000];
double sum1[150000];
double sum2[150000];
double dp1[150000];
double ans[150000];

double dfs1(int v, int p){
	int M = G[v].size();
	if(p != -1) M--;
	if(M == 0) return 0;

	for(auto c : G[v]){
		if(c == p) continue;
		sum1[v] += dfs1(c, v) + 1;
	}
	return dp1[v] = sum1[v] / M;
}

void dfs2(int v, int p){
	for(auto c : G[v]){
		if(c == p) continue;
		sum2[v] += dp1[c] + 1.0;
	}
	if(p != -1){
		if(G[p].size() != 1){
			sum2[v] += (sum2[p] - (dp1[v] + 1.0)) / (G[p].size() - 1) + 1.0;
		}
		else{
			sum2[v] += 1.0;
		}
	}
	ans[v] = sum2[v] / G[v].size();

	for(auto c : G[v]){
		if(c != p) dfs2(c, v);
	}
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	int N;
	cin >> N;
	for(int i = 0; i < N - 1; i++){
		int a, b;
		cin >> a >> b;
		a--, b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	dfs1(0, -1);
	dfs2(0, -1);
	for(int i = 0; i < N; i++){
		cout << fixed << setprecision(15) << ans[i] << endl;
	}
}

Submission Info

Submission Time
Task D - Driving on a Tree
User femto16
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1155 Byte
Status AC
Exec Time 419 ms
Memory 20480 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3
Score / Max Score 190 / 190 220 / 220 390 / 390
Status
AC × 3
AC × 2
AC × 8
Set Name Test Cases
Subtask1 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt
Subtask2 sub2_in1.txt, sub2_in2.txt
Subtask3 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt
Case Name Status Exec Time Memory
sub1_in1.txt AC 3 ms 6400 KB
sub1_in2.txt AC 6 ms 6528 KB
sub1_in3.txt AC 324 ms 17920 KB
sub2_in1.txt AC 5 ms 6528 KB
sub2_in2.txt AC 5 ms 6528 KB
sub3_in1.txt AC 419 ms 15872 KB
sub3_in2.txt AC 382 ms 15476 KB
sub3_in3.txt AC 401 ms 20480 KB