F - Colorful Tree

题意

有一个 $N$ 个节点的树，每条边有颜色、边权。

您需要处理 $Q$ 个询问，每个询问给出 $x_i,y_i,u_i,v_i$，您需要求出假定所有颜色为 $x_i$ 的边边权全部变成 $y_i$ 后，$u_i$ 和 $v_i$ 之间的距离。询问之间互相独立。

分析

DFS 序的思想套上主席树，root[i] 的权值线段树存从根到 $i$ 结点的每种颜色的边数（$cnt$），以及该颜色的长度和（$sum$）。顺便记录从根到 $i$ 结点的距离。利用差分，$dis(i, j) = dis(root, i)+dis(root, j)-2dis(root, LCA(i, j)$。然后 $i, j$ 的路径中该颜色的长度和也用同样的方法求出。那么答案就是 $dis(i, j) - \text{该颜色的长度和} + \text{该颜色的边数}*...