From 1778a649aa8ffc173c4b35a0ed849d7fb6bcea45 Mon Sep 17 00:00:00 2001
From: Trisolaris HD <36555123+TrisolarisHD@users.noreply.github.com>
Date: Sat, 30 Mar 2019 20:35:30 +0800
Subject: [PATCH] Update tree-decompose.md

---
 docs/ds/tree-decompose.md | 61 ++++++++++++++++++++++-------------------------
 1 file changed, 28 insertions(+), 33 deletions(-)

diff --git a/docs/ds/tree-decompose.md b/docs/ds/tree-decompose.md
index 770a96a3..a2a0c9ec 100644
--- a/docs/ds/tree-decompose.md
+++ b/docs/ds/tree-decompose.md
@@ -1,58 +1,53 @@
-# 树分块
+## 树分块
 
-关于树分块，可以先看一道模板题 [[SCOI2005]王室联邦](https://www.luogu.org/problemnew/show/P2325)。
+关于树分块，可以先看一道模板题 ：[「SCOI2005」王室联邦](https://www.luogu.org/problemnew/show/P2325)。
 
-这道题所要求的方式就是树分块的方式。
+这道题所要求的方案就是树分块的方案。
 
-那么如何满足**每块大小在 $[B,3B]$，块内每个点到核心点路径上的所有点都在块内**呢？
+那么如何满足**每块的大小都在区间 $[B,3B]$ 内，块内每个点到核心点路径上的所有点都在块内**呢？
 
 这里先提供一种构造方式，再予以证明：
 
-**dfs，并创建一个栈，dfs 一个点时先记录初始栈顶高度，每 dfs 完当前节点的一棵子树就判断栈内（相对于刚开始 dfs 时）新增节点的数量是否 ≥ B，是则将栈内所有新增点分为同一块，核心点为当前 dfs 的点，当前节点结束 dfs 时将当前节点入栈，整个 dfs 结束后将栈内所有剩余节点归入已经分好的最后一个块。**
+**使用 DFS 来构造，并创建一个栈，DFS 到一个点时先记录初始栈顶高度，每 DFS 完当前节点的一棵子树就判断栈内（相对于刚开始 DFS 时）新增节点的数量是否 $\geqslant B$，如果是则将栈内所有新增点分为同一块，以当前所处的点作为核心点，对当前节点的 DFS 结束时将当前节点入栈，整个 DFS 过程结束后将栈内所有剩余节点归入已经分好的最后一个块。**
 
 参考代码：
 
 ```cpp
-void dfs(int u,int fa)
-{
-    int t=top;
-    for (int i=head[u];i;i=nxt[i])
-    {
-        int v=to[i];
-        if (v!=fa)
-        {
-            dfs(v,u);
-            if (top-t>=B)
-            {
+void dfs(int u,int fa) {
+    int t = top;
+    for (int i = head[u]; i; i = nxt[i]) {
+        int v = to[i];
+        if (v != fa) {
+            dfs(v, u);
+            if (top - t >= B) {
                 ++tot;
-                while (top>t) bl[sta[top--]]=tot;
+                while (top > t) bl[sta[top--]] = tot;
             }
         }
     }
-    sta[++top]=u;
+    sta[++top] = u;
 }
 
-int main()
-{
+int main() {
     //.......
 
-    dfs(1,0);
+    dfs(1, 0);
 
-    while (top) bl[sta[top--]]=tot;
+    while (top) bl[sta[top--]] = tot;
 }
 ```
 
-如果你看懂了这个方法的话，每块大小 ≥ B 是显然的，下面证明为何每块大小≤3B：
+如果你看懂了这个方法的话，每块大小 $\geqslant B$ 是显然已经满足了的，下面证明为何每块大小均 $\leqslant 3B$：
 
 对于当前节点的每一棵子树：
 
-- 若未被分块的节点数 ≥ B，那么在 dfs 这棵子树的根节点时就一定会把这棵子树的一部分分为一块直至这棵子树的剩余节点数≤B，所以这种情况不存在。
-- 若未被分块的节点数 = B，这些节点一定会和栈中所有节点分为一块，栈中之前还剩 $[0,B-1]$ 个节点，那么这一块的大小为 $[B,2B-1]$ 。
-- 若未被分块的节点数 < B，当未被分块的节点数+栈中剩余节点数≥B时，这一块的大小为 $[B,2B-1)$，否则继续进行下一棵子树。
+- 若未被分块的节点数 $\geqslant B$，那么在 DFS 这棵子树的根节点时就一定会把这棵子树的一部分分为一块直至这棵子树的剩余节点数 $\leqslant B$，所以这种情况不存在。
+- 若未被分块的节点数 $= B$，这些节点一定会和栈中所有节点分为一块，栈中之前还剩 $[0,B-1]$ 个节点，那么这一块的大小在 $[B,2B-1]$ 内。
+- 若未被分块的节点数 $< B$，当未被分块的节点数 + 栈中剩余节点数 $\geqslant B$ 时，这一块的大小在 $[B,2B-1)$ 内，否则继续对下一棵子树执行此过程。
 
-对于dfs结束后栈内剩余节点，数量一定在 $[1,B]$ 内，而已经分好的每一块的大小为 $[B,2B-1]$，所以每块的大小都在 $[B,3B)$ 内。
+对于 DFS 结束后栈内剩余节点，其数量一定在 $[1,B]$ 内，而已经分好的每一块的大小均在 $[B,2B-1]$ 内，所以每块的大小都在 $[B,3B)$ 内。
 
-# 应用
+### 应用
 
 树分块常见的有两种应用（其实和序列上的分块类似），一种是用于莫队的，一种是不用于莫队的（废话..）。
 
@@ -84,11 +79,11 @@ $=[S(cu,root)\ xor\ S(tu,root)]\ xor\ [S(cv,root)\ xor\ S(tv,root)]$ （交换
 
 $=T(cu,tu)\ xor\ T(cv,tv)$
 
-之所以要把 $T(cu,cv)\ xor\ T(tu,tv)$ 转化成 $T(cu,tu)\ xor\ T(cv,tv)$，是因为这样的话就能通过对询问排序来保证复杂度。排序方式就是以 $u$ 所在块编号为第一关键字，$v$ 的编号为第二关键字排序。如果是带修莫队，就还要以时间为第三关键字。
+之所以要把 $T(cu,cv)\ xor\ T(tu,tv)$ 转化成 $T(cu,tu)\ xor\ T(cv,tv)$，是因为这样的话就能通过对询问排序来保证复杂度。排序方式就是以 $u$ 所在块编号为第一关键字，$v$ 的编号为第二关键字排序。如果是带修莫队，还需要以时间为第三关键字。
 
 ### 关于单点修改
 
-树上莫队的单点修改和序列莫队类似，唯一不同就是，修改后是否更新答案通过 $vis$ 数组判断。
+树上莫队的单点修改和序列莫队类似，唯一不同的地方就是，修改后是否更新答案通过 $vis$ 数组判断。
 
 ### 复杂度分析
 
@@ -96,7 +91,7 @@ $=T(cu,tu)\ xor\ T(cv,tv)$
 
 ### 例题代码
 
-[[WC2013]糖果公园](https://www.luogu.org/problemnew/show/P4074)，这题要用带修莫队，复杂度为 $\mathcal O(n^{\frac 5 3}+m\log m)$（视作 $n,m$ 同阶）。
+[「WC2013」糖果公园](https://www.luogu.org/problemnew/show/P4074)，这题要用带修莫队，复杂度为 $\mathcal O(n^{\frac 5 3}+m\log m)$（视作 $n,m$ 同阶）。
 
 ```cpp
 #include <iostream>
@@ -296,6 +291,6 @@ void add(int u,int v)
 
 在模拟赛遇到过一道题，并没有在线提交的地方，也找不到代码了..
 
-题意大概是：给你一棵点有颜色的树，每次询问给你若干条路径，要么询问这些路径的并的颜色数，要么询问这些路径的并出现的颜色的 mex（最小的未出现颜色），强制在线。节点数 $n\le10^5$，总路径条数 $m\le10^5$，颜色数 $c\le10^4$。
+题意大概是：给你一棵点有颜色的树，每次询问给你若干条路径，要么询问这些路径的并的颜色数，要么询问这些路径的并出现的颜色的 $\operatorname{mex}$（编号最小的未出现颜色），强制在线。节点数 $n\le10^5$，总路径条数 $m\le10^5$，颜色数 $c\le10^4$。
 
-std 是树分块+bitset：预处理出每块的关键点到祖先中每个关键点之间路径上颜色的 bitset，询问的时候把路径拆成两个端点分别到块内关键点、两个关键点分别到 $lca$ 所在块的下面一块的关键点、这两块的关键点分别到 $lca$，块内暴力，块的关键点到块的祖先关键点已经预处理了。时间复杂度是 $\mathcal O(n\sqrt n+m(\sqrt n+\frac c w))$（$w$ 为 bitset 的常数除以 $32$），空间复杂度为 $\mathcal O(\frac{nc}w)$。
+std 的做法是树分块+bitset：预处理出每块的关键点到祖先中每个关键点之间路径上颜色的 bitset，询问的时候把路径拆成两个端点分别到块内关键点、两个关键点分别到 $lca$ 所在块的下面一块的关键点、这两块的关键点分别到 $lca$，块内暴力，块的关键点到块的祖先关键点已经预处理了。时间复杂度是 $\mathcal O(n\sqrt n+m(\sqrt n+\frac c w))$（$w$ 为 bitset 的常数除以 $32$），空间复杂度为 $\mathcal O(\frac{nc}w)$。
-- 
2.11.0