杂题
杂题
P5021 [NOIP2018 提高组] 赛道修建
Des
给定一棵树，有边权，要求找一些简单路径，使得路径上的边无交，并且最大化最小路径长度。
Sol
看到题面直接想二分，显然答案也满足单调性。这里二分答案，问题转换为判断某个权值可不可行。
考虑如何判断。首先考虑菊花的情况，显然，任意两条边可以连成一条路径，当然，一条边也可以独自成为一条路径。
我们设现在要判断的值是 $lim$，于是把所有边权大于 $lim$ 的拿出来单独做一条路径，然后剩下的 从小的开始 看能不能找到一条边使得能凑出一条大于 $lim$ 的路径。这个过程可以二分完成。复杂度 $n\log v\log n$。
然后考虑不是菊花图的情况。因为路径不重，因此每个儿子只会传递上来一条路径，这就又变成了菊花图的情况。因此，我们首先找到儿子传递上来的边权大于等于 $lim$ 的所有边加上贡献，然后删除。对于小于 $lim$ 的情况，也是 从小的开始 尝试配对。最后，如果还有剩余没有配对的，就直接选一个最大的当做传递到父亲的边即可。复杂度 $O(n\log n\log v)$。
这里有一些坑
- 因为从小的开始，因此 **不能够匹配失败就
break**。 - 但我们同样 不能从大的开始，因为很有可能大的还要传递上去成为当前节点传递的路径。
正确性证明
首先，这里只需要证明在当前节点组成路径一定不比传递上去更劣。
考虑到传递上去也最多和其它路径构成一条路径或者自己成为一条路径，还可能会浪费掉别的一条路径，而在这里没有与之配对的边就完全没用了，因此我们不如把当前可以配对的全部配对，再把剩下的最大的传递上去，这绝对不劣。
P6655 [YsOI2020] 制高
Des
有一棵 $1$ 为根的有根树，点有点权，但我们并不清楚树的结构关系，我们只知道 $i$ 的父亲在 $l_i$ 到 $r_i$ 之间。如果 $val_x \ge val_{fa_x}$ 或 $x=1$ 则该点会产生贡献。求所有情况的贡献和。
Sol
首先，考虑到一个节点会贡献多少次取决于它的父亲的贡献概率。也就是说，如果我们已知父亲的贡献概率 $f_i$，那么显然有：
$$f_i = \frac{1}{r_i-l_i+1}\sum_{j=l_i}^{r_i}[h_i\ge h_j]f_j$$
于是我们就是用期望 $DP$，状态同上，然后转移的时候使用主席树，最后答案就是：
$$(\sum_{i=1}^nf_i)\prod_{i=1}^n(r_i-l_i+1)$$
或者，我们想想还可不可以用另一种方式求出 $f_i$。
注意到，如果我们把节点按照点权排序，那么因为大的一定不会贡献给小的，这样我们在处理最小的点权的时候就可以直接设为 $0$，然后每一次在 $l_i$ 加上 $r_i$，然后统计就可以了。这样可以做到常熟更小的 $O(n\log n)$。