题目描述：给出一棵 \(n\) 个点的树，点有颜色 \(C_i\)，长度为 \(m\) 的数组 \(V\) 和长度为 \(n\) 的数组 \(W\)。有两种操作：

1. 将 \(C_x\) 修改为 \(y\)。

2. 求 \(u\) 到 \(v\) 的链的 \(\sum\limits_{i=1}^m\sum\limits_{j=1}^{cnt_i}W_j\)，其中 \(cnt_i\) 表示颜色 \(i\) 的出现次数。

数据范围：\(n,m\le 10^5,1\le C_i\le m\)，时限6s（洛谷）或8s（UOJ）。

这是树上带修莫队的模板题。

首先我们看树分块怎么做，所以要来先做这道题。

直接讲做法了：我们是尽可能在底层把大小 \(\ge B\) 的联通块作为一块，剩下的扔给父亲合并。就是要开一个stack，维护当前还没有被分块的点。不停递归儿子，一旦已经有一个 \(\ge B\) 的连通块了，就把它们作为一块，设首都为 \(x\)（当前dfs的点）。最后把 \(x\) 放进栈中。最后递归完还要把栈中剩下的点放入最后一个块，并把首都设为 \(1\)。

inline void dfs(int x, int f){

	int t = top;

	for(Rint i = head[x];i;i = nxt[i])

		if(to[i] != f){

			dfs(to[i], x);

			if(top >= t + B){

				rt[++ num] = x;

				while(top > t) in[stk[top --]] = num;

			}

		}

	stk[++ top] = x;

}

int main(){

// ...

	dfs(1, 0);

	if(!num) num = 1;

	rt[num] = 1;

	while(top) in[stk[top --]] = num;

// ...

}

我们知道没有合并，即大小 \(<B\)，合并之后 \(<2B\)。就算最后一个连通块也至多有 \(<3B\)，所以是比较均匀的。

然后我们看看如何从链 \((u,v)\) 变为 \((u',v')\) 并且时间复杂度为 \(O(\text{len}(u,u')+\text{len}(v,v'))\)。

首先我们改为维护 \((u,v)\) 中抠掉 \(lca\) 的答案，\(cnt\) 和每个点是否在里面的 \(vis\)。设 \(L(u,v)\) 为 \(u\) 到 \(v\) 这条链上抠掉 \(lca\) 的点集，\(\oplus\) 为集合对称差（\(A\oplus B=(A\cup B)-(A\cap B)\)），\(S(u)\) 为 \(1\) 到 \(u\) 的这条链的点集。则 \(L(u,v)=S(u)\oplus S(v)\)，且集合对称差肯定是有交换、结合律的。

于是就直接是将 \(L(u,u')\) 和 \(L(v,v')\) 全部 \(vis\) 取反就是 \(L(u',v')\)，然后把 \(lca\) 取反就是 \(u'\) 到 \(v'\) 这条链。

至于带修莫队怎么做，就去看这道题。取 \(B\) 比 \(n^\frac{2}{3}\) 少一点点就可以，时间复杂度 \(O(n^\frac{5}{3}+n\log n)\)。