CF101D Castle

tony102

2021 年 09 月 24 日

2899 次浏览

3 条评论

871字数

题解

[Link](https://www.luogu.com.cn/problem/CF101D)

[51nod 1527](https://www.51nod.com/Challenge/Problem.html#problemId=1527)

## 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

```cpp
#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;
}
```

最后修改：2023 年 07 月 19 日