这道题我经过两天的激战后，我终于把它过了！
翻译：
给定一个 nnn 个节点的树，树上的第 iii 个节点有一个颜色 AiA_iAi ，编号为 iii 的边连接 Xi,YiX_i,Y_iXi ,Yi ，并且有一个值 CiC_iCi 。
定义第 iii 条边的美丽值为：
如果这条边连接的节点颜色相同（即 AXi=AYiA_{X_i}=A_{Y_i}AXi =AYi ），美丽值为 000；否则美丽值为 CiC_iCi 。
有 QQQ 次操作，每次操作会改变一个点的颜色，并且询问此时这棵树所有边的美丽值之和。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正难则反。我们预处理出所有 CiC_iCi 之和，然后减去所有连接的两个节点相同的边的 CiC_iCi 就是它的美丽值。
考虑根号分治。设置阈值为 lll，当一个点的度数大于等于 lll，则称这个点为度较多的点，否则为度较少的点。
我们可以用个哈希表 cont\tt{cont}cont，cont[i][j]\mathtt{cont}[i][j]cont[i][j] 表示当第 iii 个度较多的点颜色为 jjj 时，对美丽值的减少产生的贡献。
在查询时，对于度较少的点，直接暴力统计；而对于度较多的点，直接查表即可。得出答案后别忘了更新表。
显然度较多的点不会超过 nl\frac{n}{l}ln ，而每次查询暴力统计的点数不超过 lll，故时间复杂度为 O(ql+qnl)O(ql+\frac{qn}{l})O(ql+lqn )，当 lll 取 n\sqrt{n}n 时，时间复杂度为 O(qn)O(q\sqrt n)O(qn )。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
大功告成……了吗？
交上去会发现 MLE on #37，原来可以构造这样一个hack：
每次操作都选定最上面的节点，把每种颜色都选取一遍。显然，每次都会在 cont\tt{cont}cont 里面新增 nl\frac{n}{l}ln 个元素。此时的空间复杂度为 O(n2l)O( \frac{n^2}{l})O(ln2 )，当 l=nl=\sqrt nl=n 时为 O(nn)O(n\sqrt n)O(nn )，已经超过 256MB 的限制了。
对此，我们可以进行这样的小优化：
哈希表 cont\tt{cont}cont 只记录度较少的点对度较多的点的贡献，度较多的点之间的贡献在询问时单独计算。由于度较少的点最多只与 lll 个度较多的点相连（要是超过 lll 了就变成度较多的点了），所以每次操作在 cont\tt{cont}cont 里面新增的元素不超过 lll 个。空间复杂度就变为了 O(min{n2l,ql})O(\min\{\frac{n^2}{l},ql\})O(min{ln2 ,ql})。
而且注意到本题时间限制较为宽松，故考虑调整 lll 的大小，用时间换空间。我在这里设置的 l=200l=200l=200。
通过记录
