「随笔」CF1087D

  1. 1. 「随笔」CF1087D

「随笔」CF1087D


最近沉迷前端都没怎么写OI
青蛙子给了我这么一道题
想了半节数学课…
来吧来吧,先看看我的思路

给出一棵树,这棵树的边权总和为$s$,请输出分配边权后树直径的最小值,边权为非负整数。
嗯,我首先想二分,假如二分到的值为$s$,表示树的直径。
首先,边权为非负整数,最长链可以表示为$s[i] + s[j]$,则$s[i]$,$s[j]$一定在叶子节点处取得。所以,我们要让所有叶子节点的$s[i]$值尽量小。而如果将$1$分配给一个非叶子节点,这个$1$能影响一个及以上的$s$,所以贪心思考,尽量把数值放到叶子节点去。这样,我每个叶子节点都安排为$\frac{s}{2}$,安排$cnt - 1$个叶子节点后,如果剩下的一个$\ge \frac{s}{2}$,则不行。否则可以。
当然,因为$check$是$O(1)$的,这段还可以用数学公式解。
两个月没学OI居然还想得出题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, s, cnt, head[N], in[N], ver[N << 1], nxt[N << 1], tot;
inline void addedge(int u, int v) {
ver[tot] = v;
nxt[tot] = head[u];
++in[u], ++in[v];
head[u] = tot++;
}
inline void dfs(int x, int fa) {
int fg = 0;
for (int i = head[x], to; ~i; i = nxt[i])
if ((to = ver[i]) != fa)
fg = 1, dfs(to, x);
cnt += fg == 0 ? 1 : 0;
}
int main() {
memset(head, -1, sizeof head);
scanf("%d%d", &n, &s);
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
dfs(1, 0);
if (in[1] == 2) ++cnt;
double l = 0, r = s, mid;
while (r - l >= 1e-7) {
mid = (l + r) / 2;
if (s - (cnt - 1) * (mid / 2) <= (mid / 2)) r = mid;
else l = mid;
}
printf("%.8lf", l);
}