CF101D_Castle

Problem

题目蓝链

推荐不要看原题面，原题题面已经过转化

一颗n个点的带边权且以一号点为根的有根树，边权为走这条边所要花的时间

树上有一个宝箱位于一号点以外的点，但是不知道宝箱具体在那个点

如果有一个人从一号点出发，每条边只能走不超过2次，按照最优策略走，问找到宝藏的期望时间。

(n leq10^5,边权leq1000)

Solution

一开始看到这道题，完全不知道要干什么

那就只能转化题目

令(t_i)表示第一次到达(i)点的时间

题目要求的期望就变成了

[frac{sum_{i = 1}^{i leq n}t_i}{(n - 1)} ]

然后我们就可以贪心了

定义点(x)的点权(val_x)为遍历(x)为根的子树所需要的时间与子节点个数的比值。

所以对于每个节点(x)的儿子,我们按照(val)从小到大排序后再按顺序遍历就可以了

Code

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

inline int read(){
	int res = 0, fl = 1;
	char r = getchar();
	for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
	for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
	return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
const int Maxn = 2e5 + 10;
vector<pii>g[Maxn];
long double val[Maxn];
int siz[Maxn];
void dfs(int now, int pa){
	siz[now] = 1;
	for (int i = g[now].size() - 1; i >= 0; --i){
		int nxt = g[now][i].fst;
		if(pa == nxt) continue;
		//val[now] += g[now][i].snd;
		val[nxt] += g[now][i].snd;
		dfs(nxt, now);
		val[now] += val[nxt];
		siz[now] += siz[nxt];
	}
}
LL Time, t[Maxn];
bool cmp(pii A, pii B){
	return val[A.fst] > val[B.fst];
}
void Dfs(int now, int pa){
	for (int i = g[now].size() - 1; i >= 0; --i){
		int nxt = g[now][i].fst;
		if(nxt == pa) continue;
		val[nxt] = 1.00 * val[nxt] / siz[nxt];
	}
	sort(g[now].begin(), g[now].end(), cmp);
	t[now] = Time;
	for (int i = g[now].size() - 1; i >= 0; --i){
		int nxt = g[now][i].fst;
		if(pa == nxt) continue;
		Time += g[now][i].snd;
		Dfs(nxt, now);
		Time += g[now][i].snd;
	}
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int n = read();
	for (int i = 1; i < n; ++i){
		int x = read(), y = read(), z = read();
		g[x].push_back(mp(y,z));
		g[y].push_back(mp(x,z));
	}
	dfs(1, 0);
	Dfs(1, 0);
	long double ans = 0;
	for (int i = 1; i <= n; ++i) ans += t[i];
	printf("%.6Lf
",1.00 * ans / (n - 1));
	return 0;
}