東京

冷却心 · 2026-08-11 16:16:47 · 题解

考察子问题给定一棵树如何计算答案。考虑一个更简单的问题，对权值进行切分，对于一个阈值 w，记 b_i=[a_i>w]，问这个 01 权值的树会造成多少贡献。

对于 01 权值的树，如果整棵树都是同色显然没有贡献不再讨论。很容易发现最优方案是把所有的 1 连通块零代价地合并成一个，然后和旁边的 0 用 1 的代价合并，换言之，贡献是 1 连通块的个数。考虑如何简单刻画 1 连通块的个数。考察 1 连通块的根，注意到连通块个数等于一个点是 1 且其父亲是 0 的点的个数加上树根是否是 1。

对于任意权值，我们考虑一条边在多少种阈值 w 切分的情况下会有贡献，根据上面的讨论，记这条边的父亲是 u 儿子是 v，他会产生贡献当且仅当 a_u\le w \wedge a_v>w，故贡献为 \max(0,a_v-a_u)。当然我们还未计算根的贡献，根只要满足他大于 w 且树不全大于 w 就有贡献，所以贡献为 a_r-x，其中 a_r 是树根权值，x 是树权值的最小值。

不带修的话对每个子树维护一下子树最小值和每个点对父亲的贡献即可。

带修改比较麻烦。根的贡献只需要单点修改求子树最小值，线段树直接维护。一般的贡献，我们考虑维护 s_u 表示 \sum \max(0,a_u-a_v)，其中 v 是 u 的所有儿子，那么每次单点修改只会改 u 和其父亲的 s 值，再开一颗树状数组或者线段树单点修改 dfn 区间和。维护对父亲的 s 的修改很简单，减去之前的贡献加上新的贡献即可。但是维护自己的 s 值比较困难，枚举所有的 v 复杂度错误，故对每个节点维护其所有儿子的权值集合，支持查询大于某个数的个数以及总和，用动态开点权值线段树即可。复杂度 1log。