题意：给出一个有$N$个点的树，你最开始在$1$号点，经过第$i$条边需要花费$w_i$的时间。每条边只能被经过$2$次。求出到达除$1$号点外所有点的最早时间的最小平均值。$N \leq 10^5 , w \leq 1000$
设$f_i$表示以第$i$个点为子树的最小总时间，考虑由儿子向父亲合并，额外定义$dis_i$为$i$到其父亲的边的边权，$t_i$表示从$t$的父亲走完根节点为$t$的子树再回到$t$的时间，也就等于$(\text{子树边权和+与父亲相连的边的边权})\times 2$，再定义$size_i$表示以$i$为根节点的子树的点数。可以$t_i$与$size_i$都是很容易从儿子向父亲合并的。
设我们正在算点$x$的答案，其儿子为$y_1,y_2...y_k$，且它们的答案已经算出来了。那么它的父亲的答案也就是$\sum\limits_{i=1}^k (f_{y_i}+dis_i \times size_i) + \sum\limits_{i=1}^k t_{p_i} \times (size_x - 1 - \sum\limits_{j=1}^i size_{p_i})$，其中$p_1,p_2...p_k$是一个$y_1,y_2...y_k$的排列，因为子树的选择是无序的，而在选择某个子树的时候，剩下没有选的所有点都需要等待这棵子树遍历完。
那么现在我们的任务转变为了找到一个最优的$p_1,p_2...p_k$的选择。考虑这个排列可能与排序有关，所以我们使用邻项交换的方法分析是否具有贪心策略。考虑相邻两个元素$p_i,p_i+1$，因为交换对于其他元素的答案是没有影响的，所以我们只需要考虑$p_i$与$p_{i+1}$的差别，将其他的设为$W$。
当我们的顺序是$p_i,p_{i+1}$时，答案是$f_{p_i}+t_{p_i} \times size_{p_{i+1}}+f_{p_{i+1}}+W$，而当顺序为$p_{i+1},p_i$时答案为$f_{p_{i+1}}+t_{p_{i+1}} \times size_{p_i}+f_{p_i}+W$。我们令第一种方案优于第二种方案，所以$f_{p_i}+t_{p_i} \times size_{p_{i+1}}+f_{p_{i+1}}+W < f_{p_{i+1}}+t_{p_{i+1}} \times size_{p_i}+f_{p_i}+W$，可以得到$t_{p_i} \times size_{p_{i+1}} < t_{p_{i+1}} \times size_{p_i}$。所以我们使用这个公式进行排序，就可以得到最优的方案。
#include<bits/stdc++.h>
#define ld long double
#define MAXN 500010
#define int long long
using namespace std;
inline int read(){
;
;
char c = getchar();
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
struct Edge{
int end , upEd , w;
}Ed[MAXN];
int head[MAXN] , siz[MAXN] , T[MAXN] , N , cntEd , forC;
ld dp[MAXN];
bool cmp(int a , int b){
return T[a] * siz[b] < T[b] * siz[a];
}
inline void addEd(int a , int b , int c){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
Ed[cntEd].w = c;
head[a] = cntEd;
}
void dfs(int now){
siz[now] = ;
vector < int > v;
for(int i = head[now] ; i ; i = Ed[i].upEd)
if(!siz[Ed[i].end]){
dfs(Ed[i].end);
siz[now] += siz[Ed[i].end];
T[Ed[i].end] += Ed[i].w << ;
dp[Ed[i].end] += Ed[i].w * siz[Ed[i].end];
v.push_back(Ed[i].end);
}
sort(v.begin() , v.end() , cmp);
; i < v.size() ; i++){
dp[now] += T[now] * siz[v[i]] + dp[v[i]];
T[now] += T[v[i]];
}
}
main(){
N = read();
; i < N ; i++){
int a = read() , b = read() , c = read();
addEd(a , b , c);
addEd(b , a , c);
}
dfs();
cout << ) << dp[] * );
;
}