考虑把查询拆成一端点为 \(1\) 的 \(3\) 个查询。
那么要维护一个点 \(x\) 到 \(1\) 号点的路径长度，某种颜色的边权和与出现数量。
这个显然可以用可持久化线段树维护，时间复杂度 \(O((n + q)\log n\)，空间 \(O(n\log n)\)。
ABC133F Colorful Tree
发布时间 2023-05-08 10:28:25作者: CJzdc
考虑把查询拆成一端点为 \(1\) 的 \(3\) 个查询。
那么要维护一个点 \(x\) 到 \(1\) 号点的路径长度，某种颜色的边权和与出现数量。
这个显然可以用可持久化线段树维护，时间复杂度 \(O((n + q)\log n\)，空间 \(O(n\log n)\)。