树上莫队
括号序树上莫队
一般的莫队只能处理线性问题，我们要把树强行压成序列．
我们可以将树的括号序跑下来，把括号序分块，在括号序上跑莫队．
具体怎么做呢？
过程
dfs 一棵树，然后如果 dfs 到 x 点，就 push_back(x)，dfs 完 x 点，就直接 push_back(-x)，然后我们在挪动指针的时候，
- 新加入的值是 x --->
add(x) - 新加入的值是 - x --->
del(x) - 新删除的值是 x --->
del(x) - 新删除的值是 - x --->
add(x)
这样的话，我们就把一棵树处理成了序列．
例题
例题 「WC2013」糖果公园
题意：给你一棵树，树上第 𝑖i
个点颜色为 𝑐𝑖ci，每次询问一条路径 𝑢𝑖ui,𝑣𝑖vi, 求这条路径上的
∑𝑐𝑣𝑎𝑙𝑐∑𝑐𝑛𝑡𝑐𝑖=1𝑤𝑖∑cvalc∑i=1cntcwi
其中：𝑣𝑎𝑙val 表示该颜色的价值，𝑐𝑛𝑡cnt 表示颜色出现的次数，𝑤w 表示该颜色出现 𝑖i 次后的价值
过程
先把树变成序列，然后每次添加/删除一个点，这个点的对答案的贡献是可以在 𝑂(1)O(1) 时间内获得的，即 𝑣𝑎𝑙𝑐 ×𝑤𝑐𝑛𝑡𝑐+1valc×wcntc+1
发现因为他会把起点的子树也扫了一遍，产生多余的贡献，怎么办呢？
因为扫的过程中起点的子树里的点肯定会被扫两次，但贡献为 0．
所以可以开一个 𝑣𝑖𝑠vis 数组，每次扫到点 x，就把 𝑣𝑖𝑠𝑥visx 异或上 1．
如果 𝑣𝑖𝑠𝑥 =0visx=0，那这个点的贡献就可以不计．
所以可以用树上莫队来求．
修改的话，加上一维时间维即可，变成带修改树上莫队．
然后因为所包含的区间内可能没有 LCA，对于没有的情况要将多余的贡献删除，然后就完事了．
实现
参考代码
---|---
## 真·树上莫队
上面的树上莫队只是将树转化成了链，下面的才是真正的树上莫队．
由于莫队相关的问题都是模板题，因此实现部分不做太多解释
### 询问的排序
首先我们知道莫队的是基于分块的算法，所以我们需要找到一种树上的分块方法来保证时间复杂度．
条件：
* 属于同一块的节点之间的距离不超过给定块的大小
* 每个块中的节点不能太多也不能太少
* 每个节点都要属于一个块
* 编号相邻的块之间的距离不能太大
了解了这些条件后，我们看到这样一道题 [「SCOI2005」王室联邦](https://loj.ac/problem/2152)．
在这道题的基础上我们只要保证最后一个条件就可以解决分块的问题了．
思路
令 lim 为希望块的大小，首先，对于整个树 dfs，当子树的大小大于 lim 时，就将它们分在一块，容易想到：对于根，可能会剩下一些点，于是将这些点分在最后一个块里．
做法：用栈维护当前节点作为父节点访问它的子节点，当从栈顶到父节点的距离大于希望块的大小时，弹出这部分元素分为一块，最后剩余的一块单独作为一块．
最后的排序方法：若第一维时间戳大于第二维，交换它们，按第一维所属块为第一关键字，第二维时间戳为第二关键字排序．
### 指针的移动
#### 过程
容易想到，我们可以标记被计入答案的点，让指针直接向目标移动，同时取反路径上的点．
但是，这样有一个问题，若指针一开始都在 x 上，显然 x 被标记，当两个指针向同一子节点移动（还有许多情况）时，x 应该不被标记，但实际情况是 x 被标记，因为两个指针分别标记了一次，抵消了．
如何解决呢？
有一个很显然的性质：这些点肯定是某些 LCA，因为 LCA 处才有可能被重复撤销导致撤销失败．
所以我们每次不标记 LCA，到需要询问答案时再将 LCA 标记，然后再撤销．
#### 实现
---|---
对于求 LCA，我们可以用树剖，然后我们就可以把分块的步骤放到树剖的第一次 dfs 里面，时间戳也可以直接用第二次 dfs 的 dfs 序．
---|---
### 时间复杂度
重点到了，这里关系到块的大小取值．
设块的大小为 𝑢𝑛𝑖𝑡unit：
* 对于 x 指针，由于每个块中节点的距离在 𝑢𝑛𝑖𝑡unit 左右，每个块中 x 指针移动 𝑢𝑛𝑖𝑡2unit2 次（𝑢𝑛𝑖𝑡 ×𝑑𝑖𝑠maxunit×dismax），共计 𝑛 ×𝑢𝑛𝑖𝑡n×unit 次（𝑢𝑛𝑖𝑡2 ×(𝑛𝑢𝑛𝑖𝑡)unit2×(nunit)）；
* 对于 y 指针，每个块中最多移动 𝑂(𝑛)O(n) 次，共计 𝑛2𝑢𝑛𝑖𝑡n2unit 次（𝑛 ×(𝑛𝑢𝑛𝑖𝑡)n×(nunit)）．
加起来大概在根号处取得最小值（由于树上莫队块的大小不固定，所以不一定要严格按照）．
### 例题「WC2013」糖果公园
由于多了时间维，块的大小取到 𝑛0.6n0.6 的样子就差不多了．
参考代码
---|---
本页面最近更新： 2026/4/23 03:45:48，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：countercurrent-time, H-J-Granger, StudyingFather, Ir1d, NachtgeistW, Tiphereth-A, Enter-tainer, AngelKitty, CCXXXI, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, Konano, LovelyBuggies, Makkiy, mgt, minghu6, P-Y-Y, PotassiumWings, SamZhangQingChuan, sshwy, Suyun514, weiyong1024, Backl1ght, c-forrest, Chrogeek, GavinZhengOI, Gesrua, greyqz, Henry-ZHR, iamtwz, ImpleLee, ksyx, kxccc, lailai0916, Ling✨, Linky, Lookcatbox, lychees, MicDZ, ouuan, Peanut-Tang, SukkaW, yzxoi 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用