Sol
答案是非常好表示的,设 $p_i$ 表示某个点访问儿子的顺序, $f_i$ 为以 $i$ 为根的子树的最小时间。
因为子树中每一条边都要进去一次出去一个,进入和离开当前子树都要通过当前子树根与其父亲相连的边,我们用 $sum_i$ 就是当前子树内边权和与通往父亲那条边的总和 $\times 2$
那么:
$$ f_i = \sum\limits_{i=1}^{son_{i}} f_{p_i} + (\sum\limits_{j=1}^{i-1} sum_{p_j})\cdot siz_{p_i} $$
前面加号前的东西值是不变的,现在要最小化后面那个东西。
考虑交换 $p_{i}$ 和 $p_{i+1}$ ,那么若 $siz_{p_i}\cdot sum_{p_{j+1}} - siz_{p_{j+1}} \cdot sum_{p_j} < 0$ 那么显然交换更优,那么也就是转移的时候用一个数组把这个东西记下来然后升序排序,从最小值开始取可以使答案最小。
Code
#include <bits/stdc++.h>
using namespace std;
typedef pair < double, double > PDD;
typedef vector < PDD > vec;
const int SIZE = 1e5 + 5;
int n, num;
int head[SIZE]; double f[SIZE], siz[SIZE], sum[SIZE];
struct node {
int to, v, nxt;
} edge[SIZE << 1];
namespace GTR {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (c < 48 || c > 57) b ^= c == '-', c = fetch();
while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
return b ? a : -a;
}
} using GTR::read;
void addEdge(int u, int v, int d) {
edge[++ num] = (node) {v, d, head[u]}, head[u] = num;
}
void dfs(int u, int fa) {
siz[u] = 1.000; vec tmp;
for (int i = head[u], v; i; i = edge[i].nxt) {
v = edge[i].to;
if (v == fa) continue;
dfs(v, u);
f[u] += edge[i].v * siz[v] + f[v], siz[u] += siz[v], sum[u] += 2.000 * edge[i].v + sum[v];
tmp.emplace_back((PDD) {sum[v] + 2.00 * edge[i].v, siz[v]});
}
if (!tmp.empty())
std::sort(tmp.begin(), tmp.end(), [] (PDD a, PDD b) { return a.first * b.second < b.first * a.second; });
double s = 0;
for (PDD it: tmp) f[u] += s * it.second, s += it.first;
}
int main() {
// freopen("code.in", "r", stdin);
n = read();
for (int i = 1, u, v, d; i < n; ++ i) {
u = read(), v = read(), d = read();
addEdge(u, v, d); addEdge(v, u, d);
}
dfs(1, 0);
printf("%.7lf\n", f[1] / (n - 1));
return 0;
}
3 条评论
托神无敌
托神无敌
托神无敌