思路:
该题是树上莫队的模板。除去和树有关的部分,“不同颜色数”也是很常见的莫队题型。
和树链相关的问题可以使用欧拉序解决。
欧拉序是一种特殊的dfs序,每个点在序列中会被记录两次:进入该节点时和访问完该节点的子树时。
使用欧拉序后就可以将树链的询问变为区间的询问:每个不在指定树链上的点要么不出现,要么出现两次,可以通过这一点来去掉这些点的贡献。
一个特例是当$lca(x,y) \neq x \lor y$时的$lca(x,y)$,由于x,y均在其lca的子树中,所以$lca(x,y)$不会出现在x,y的欧拉序区间中,此时需要额外加上lca的贡献。
同时注意欧拉序长度为2n,块长需要设置为$\sqrt{2n}$。
代码:
1 |
|