【MX-X8-T7】「TAOI-3」2236 A.D.

【MX-X8-T7】「TAOI-3」2236 A.D.

对于每个点 \(x\)，计算出满足 \(\text{lca}(u,v)=x\) 的路径 \((u,v)\) 对应的权值和。

我们对于每个点 \(x\)，考虑所有 \(y \in \text{subtree}(x)\) 对应的路径 \((y,x)\)。

我们记 \((y,x)\) 路径上经过的颜色集合为 \(S_{y,x}\)。

同时，记 \(f_S\) 表示颜色集合为 \(S\) 对应的权值之和。

发现一个点 \(y\) 在 \(x\) 向上跳时 \(S_{y,x}\) 只会变 \(O(k)\) 次。

我们对于每个点 \(x\) 记录一个桶 \(a_x\)，其中 \(a_{x,i}\) 表示 \(S_{y,x}=i\) 的路径条数。

使用 dsu on tree 维护桶，显然桶只会被修改 \(O(n \log n + nk)\) 次。

接下来考虑查询，相当于给定 \(p\)，查询下式的值：

\[\sum\limits_{q} a_{x,q} \times f_{p \lor q} \]

显然我们的修改是 \(O(1)\) 的，查询是 \(O(2^k)\) 的。

我们记 \(x\) 的前 \(\dfrac{x}{2}\) 位为 \(x_1\)，后 \(\dfrac{x}{2}\) 位为 \(x_2\)。

显然，\(f_x = f_{x_1} \times f_{x_2}\)。

接下来考虑重新描述答案，即：

\[\sum\limits_{q} a_{x,q} \times f_{p_1 \lor q_1} \times f_{p_2 \lor q_2} \]

显然其等于：

\[\sum\limits_{q_1} f_{p_1 \lor q_1} \sum\limits_{q_2} a_{x,q} \times f_{p_2 \lor q_2} \]

维护 \(g_{q_1,p_2}\) 表示 \(\sum\limits_{q_2} a_{x,q} \times f_{p_2 \lor q_2}\)。

显然，我们在询问时只需要 \(O(2^{\frac{k}{2}})\) 枚举 \(q_1\) 即可。

接下来考虑修改操作，考虑枚举 \(p_2\)。

此时由于我们已知了修改的 \(q\)，将对应的 \(g\) 加减即可。

时间复杂度 \(O((n \log n + nk)2^{\frac{k}{2}})\)。