「BJOI2017」树的难题 题解

核心思路 点分治 + 单调队列/线段树优化

关键转化 路径权值 = 所有边颜色权值和 - 相邻同色边的前一条颜色权值和 即：拼接两条路径时，若接头处颜色相同，需减去一次该颜色权值。

算法步骤

点分治枚举路径必经重心 $rt$

对 $rt$ 的每棵子树：

遍历得到路径 $(dep, val, lastcol)$

查询之前子树中深度在 $[l-dep, r-dep]$ 的路径：

若最后颜色不同：权值 = $val + f[t]$

若相同：权值 = $val + f[t] - w_{col}$

用单调队列维护按深度排序的路径，对每种颜色维护最大值

更新答案，并将当前子树加入数据结构

数据结构优化 对每个深度 $t$ 维护：

全局最大值 $best1[t]$ 及其颜色

全局次大值 $best2[t]$

每种颜色单独的最大值 $f[t][c]$

查询时： $\max(\max_{c\neq lc} best1/best2, f[t][lc]-w_{lc})$

用线段树维护区间最大值，支持单点更新。

时间复杂度

$O(n \log^2 n)$，可通过 $n \leq 2\times 10^5$。