树上单点修改 $+$ 树上路径查询，且路径难以用树剖维护。
考虑先将树转化为括号序列，设结点 $u$ 对应的左括号编号为 $\text{dfn}_{1u}$，右括号编号为 $\text{dfn}_{2u}$。
对当前维护的括号序列区间 $[l,r]$，仅计算 $[l,r]$ 中未匹配的括号代表的结点的贡献。
即某个结点第奇数次出现时加上该结点的贡献，第偶数次出现时减去该结点贡献。
于是对每个询问路径 $u\to v$，不妨设 $\text{dfn}_{1u}\le \text{dfn}_{1v}$。
如果 $u$ 为 $v$ 的祖先，则路径对应区间为 $[\text{dfn}_{2u},\text{dfn}_{1v}]$。
否则路径对应区间为 $[\text{dfn}_{2u},\text{dfn}_{1v}] + \text{LCA}(u,v)$。
对于修改操作，如果修改的点在当前区间中且出现奇数次，则考虑更新答案，否则直接更新该点权值即可。
给定一棵树，树上每个点有一种颜色，总共有 $m$ 种颜色。同时给定序列 $\{v_i\},\{w_i\}$。
要求支持单点颜色修改操作和路径权值查询操作。设一条路径上颜色为 $i$ 的颜色出现了 $c_i$ 次，则该路径的权值为
$$ \sum_{i=1}^mv_i\sum_{j=1}^{c_i}w_j $$
树上莫队板子题。
普通莫队仅适用于当询问得区间拓展/删除都可以 $O(1)$ 维护的情况。
其中有一种操作难以 $O(1)$ 维护时，可以利用回滚莫队仅维护一种操作，时间复杂度仍为 $O(n\sqrt m)$，只是常数增大。
设块大小为 $S$，当询问的左右端点都属于同一个块时，可以 $O(S)$ 暴力处理。
剩下的询问先按左端点分块，然后按右端点从小到大排序。
对每个块 $[l,r]$ 中的询问，先初始化当前莫队区间的右端点为 $r$，左端点为 $r+1$。
莫队区间的右端点仍然单增，于是每个块的右端点移动仍可以 $O(n)$ 维护。
对莫队区间的左端点每次都从 $r+1$ 开始重新向左拓展，然后每次处理完询问后再回滚到 $r+1$。注意回滚仅回滚左端点不回滚右端点。
于是每个询问的左端点移动可以 $O(S)$ 维护。总时间复杂仍为 $O\left(ms+\frac {n^2}S\right)$，取 $S=O\left(\frac n{\sqrt m}\right)$，时间复杂度为 $O(n\sqrt m)$。
另外注意当跑到另一个块时需要消除之前的右端点影响，可以考虑暴力清空(因为只有 $O(S)$ 个块)，也可以回滚上一个块的右端点。
给定一个序列，每个询问序列区间 $[l,r]$。设区间 $[l,r]$ 中数 $i$ 出现 $c_i$ 次，求 $\max(i*c_i)$。
显然对于区间拓展操作，答案很容易维护，但区间删除操作答案难以维护。
直接套回滚莫队板子即可。
给定一个长度为 $n$ 的序列 $A$，接下来有 $q$ 个询问。每次询问给定 $l,r,k$，求
$$ \sum_{i=0}^{k-1}f(l-i,r+i)(n+1)^i $$
其中 $f$ 定义如下
$$ f(l,r)=\max(\{k|\exists x\forall i(0\le i\le k-1\to \exists j(l\le j\le r,a_j=x+i))\}) $$
考虑回滚莫队处理询问，难点在于怎么维护最大的 $k$。
实际上，这等价于维护数轴上的最长连续线段。可以令 $\text{vl}(x)$ 表示以数 $x$ 为左端点的线段在数轴上的右端点。
$\text{vr}(x)$ 表示以数 $x$ 为右端点的线段在数轴上的左端点。于是只需要保证每条线段的两个端点的 $\text{vl},\text{vr}$ 正确性即可，不难 $O(1)$ 维护。
时间复杂度 $O\left(n\sqrt q+\sum k\right)$。
给定长度为 $n$ 的序列 $a$ 和 $m$ 个询问。
每个询问给定 $[l_1,r_1],[l_2,r_2],[l_3,r_3]$，不断删去三个区间中的相同元素，直到三个区间不存在相同元素，问三个区间剩下的数的个数和。
例如，给定序列 $1,1,1,2,3$，询问区间 $[1,3],[2,4],[3,5]$，进行删去操作后三个区间元素为 $\{1\},\{2\},\{2,3\}$。
不难发现答案为 $r_1-l_1+r_2-l_2+r_3-l_3+3-s$，其中 $s$ 为公共元素的个数。
考虑维护每个原询问对应的公共元素的 $\text{bitset}$，初始时全为 $1$，记为 $s_i$。将原询问拆成三个询问区间丢掉莫队。
$\text{bitset}$ 维护莫队区间元素，记为 $\text{cur}$。每次处理询问只需要将当前询问对应对应 $s_i$ 更新为 $s_i\text{&cur}$ 即可。
但是不难发现 $\text{bitset}$ 不支持重复元素，于是进行如下改造。
定义 $b_i$ 为序列 $a$ 中不大于 $a_i$ 的位置的个数，然后当 $a_i$ 在莫队区间第 $c_i$ 次出现时，将 $b_i-c_i$ 加入 $\text{bitset}$。
另外需要维护 $m$ 个 $s_i$，于是空间复杂度为 $O(\frac {nm}{w})$ 难以承受。考虑将询问分成三份，于是空间复杂度变为原来的 $\frac 13$。
原时间复杂度 $O(n\sqrt m+\frac{nm}{w})$。另外由于询问分成了三份，于是新时间复杂度为 $O(n\sqrt {3m}+\frac{nm}{w})$。