P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

· · 题解

路径加可以树上差分。即令 res_{i, j} 表示答案中第 i 个节点上 j 种类的数量，d_{i, j} 为其差分数组。每次操作 (x, y, z) 等价于：

d_{x,z} \gets d_{x, z} + 1 \\ d_{y,z} \gets d_{y, z} + 1 \\ d_{lca,z} \gets d_{lca, z} - 1 \\ d_{fa_{lca},z} \gets d_{fa_{lca}, z} - 1

发现 d_{i, 1\sim n} 可以用线段树维护，而最后做一次前缀和的过程为线段树合并。