题面
给定一个花园，有\(N\)个温室，构成一棵树。每个温室种一种花，第\(i\)个温室种类为\(T_i\)。给定\(Q\)个操作，操作为下面两种形式之一：
- \(C x t\)：表示在温室\(x\)中的花种类变为\(t\)
- \(Q x y t\)：表示查询\(x\)到\(y\)的路径中种类为\(t\)的花出现几次
操作必须在线。每次\(x,y,t\)要亦或上次查询的答案。
\(1≤N,Q≤2×10^5\)，\(T_i\)和\(t\)均为int范围内的整数。
题解
\(t\)范围过大，且要求在线，不能离散化，那就用map映射。
查询操作让我们想到了LCA。设\(x\)和\(y\)的LCA为\(z\)，那么总次数=\(x\)到\(z\)的次数+\(y\)到\(z\)的次数。凭经验，我们设\(s_{x,t}\)表示\(x\)到根节点中种类为\(t\)的花的个数。那么答案=\(s_{x,t}+s_{y,t}-2×s_{z,t}+(T_z==t)\)。
发现，在修改操作之后，以\(x\)为根的子树中所有节点\(i\)的\(s_{i,T_x}\)减1，\(s_{i,t}\)加1。是不是有点线段树的感觉？但这里的“区间”是一整棵子树，而不是抽象的“线段”。
子树转化为区间的常用技巧是求dfs序，因为在dfs序中，一棵子树中的所有点一定连在一起。此题可以使用这种方法。按照dfs序的顺序维护所有节点，每次\(C\)操作修改一段连续的区间。但我们又面临着一个问题：要求维护的信息（即\(s\)）会根据\(x\)的变化而变化，一棵线段树无法解决问题。
那么就对每个节点再开一棵线段树，变成线段树套线段树。每个节点的线段树中以花的种类作为“下标”，维护\(s\)。利用动态开点，空间可以承受。然而，稍加分析会发现：这时懒惰标记向下传递会十分困难，因为其不满足“区间可加性”（PS：对线段树，尤其是懒惰标记的实现而言，这一点非常重要）。
再换一种方法。我们对每个种类开一棵线段树，“下标”为dfs序，权值为\(s\)。再回顾一边两种操作。\(C\)操作，只需分别在\(T_x\)和\(t\)的树中区间修改（此时懒惰标记可以“加”）；\(Q\)操作，在\(t\)的树中单点查询。于是问题解决。
Code
#include
#include
#include