2021.11.15模拟赛

Turned into a moon that always tells the warmth and brightness of the sun

2021.11.15 模拟赛

某种意义上的信心赛？

想一下应该是二分，因为肯定是取前 $k$ 小个所以二分不能取得最小值

排完序后依次扫可以发现每个合法区间的右端点有单调性，就可以 $O(n)$ 判断

$G \le 16$ 状压，先跑 bfs 预处理出来关键点之间两两最短路

然后状压 dp 转移即可

$O(n\times \mathrm{dep})$ 暴力过了，数据真就硬随

考虑深度为 $i$ 的点只需要用到深度为 $i-1$ 的点的信息，所以逐层拓展

每个点会给他到根的每个点的权值乘上一个自己的概率（对于下一层受到影响的点来说）

而每个点的答案就是自己到根上权值的乘积

树剖维护即可

树形依赖背包，按 dfs 序转移即可