Решение задачи Путешествие с Codeforces

Без пояснения   Просмотров: 70

В Семи Королевствах n городов и n - 1 дорога, каждая дорога соединяет два города, и возможно достичь каждый город из каждого, передвигаясь по дорогам.

Теон и Яра Грейджой начинают путешествовать на лошади по дорогам из первого города. Из-за тумана они не видят, куда лошадь их везет. Когда лошадь входит в город (в том числе в первый), она направляется в один из городов, соединенных с ним. Но это странная лошадь, поэтому она пойдет только в город, в котором до этого не была. Она идет равновероятно в каждый из таких городов и останавливается, если таких городов нет.

Пусть длина каждой дороги 1. Путешествие начинается в городе 1. Чему равно математическое ожидание длины их путешествия? Формально, математическое ожидание — это ожидаемое (то есть среднее) значение. Подробнее можно прочесть по ссылке https://ru.wikipedia.org/wiki/Математическое_ожидание.

Код 

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 100100;

int n, a, b, d;
vector<int> g[MAXN];
bool pro[MAXN];

double dfs(int v){
	pro[v] = 1;
	double soma = 0.0;
	bool leaf = true;
	int div = 0;
	for(auto u : g[v]){
		if(pro[u])
			continue;
		soma += dfs(u);
		div++;
		leaf = false;
	}
	if(leaf) return 0.0;
	return (soma/div) + 1.0;
}

int main(){
	cin >> n;
	for(int i = 0;i < n-1;i++)
		cin >> a >> b, g[a].push_back(b), g[b].push_back(a);
	cout << fixed << setprecision(6) << dfs(1) << endl;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта