我们对树重链剖分，用类似动态 DP 的方法来维护。

我们用 multiset 维护每个点的轻子树，每棵子树的信息有子树的答案以及子树的最长链（这条链的 $a,c$ 是确定的）。如果一条链的 LCA 是 $x$ 且两端都是 $x$ 的轻子树，则一定是取满足 $a=a_x$ 的 $(a,c)$ 的最长两条链求和的最大值。对于每个 $a$，我们维护每个 $c$ 的最长两条链的和，这在轻子树信息改变时可以 $O(1)$ 次 multiset 操作维护。然后我们就可以在 $O(1)$ 次 multiset 操作中查询一个 $a$ 的值。

再来考虑重链的情况。我们可以把每条边的 $c$ 放在它下面的点上。那么在重链上的路径可以分成三段：设当前点是 $x$，重链上的下一个点是 $y$

• 最顶端的部分，要求 $a_x=a_y$，权值等于轻子树中等于 $(a_y,c_y)$ 的最长链。
• 中间的部分，要求 $(a_x,c_x)=(a_y,c_y)$，权值等于 $w_x$。
• 最底端的部分，没有要求，权值等于轻子树中等于 $(a_x,c_x)$ 的最长链加上 $w_x$。

我们可以用线段树维护重链上的信息合并，求出经过 LCA 所在重链的答案，以及子树内的最长链。修改 $x$ 的颜色时，只需要先去除到根的每条重链的贡献，然后更新 $x$ 和 $p_x$ 的信息，之后不断跳重链并加入贡献、更新信息。

时间复杂度 $O((n+q\log n)\log n)$。