D

长为l的路径,人的速度为v1,车的速度为v2,有n个人,车的容量为k
问最少时间走完l

解方程

显然,每个人坐车的距离一致设为a,而且每个人到达终点的时间也一致
设车把人送到一个位置再回来接人的时间为t,除最后一次都要回来

$v_1t + v_2(t-a/v_2) = a$
$t = 2a/(v_1+v_2)$
$t(\lceil n/k \rceil - 1) = (l-a)/v_1$
$a = (v_1 + v_2)l/(v_1 + v_2 + 2(\lceil n/k \rceil - 1)v_1)$
$ans = a/v_2 + (l-a)/v_1$

E

一棵树上有2k个点,使其两两配对
现求这k个点的一种配对使得配对的路径长度和最大
求最大的路径长度和

树形dp

显然考虑路径要经过尽量多的边
因此对于每一条边,我们求其两端点的标记的点个数最小值
即$min(sz[v],2k-sz[v])$
全部加起来就是答案