From 19e0a43a994a7adc37cf54ff4a6b758fd707c1d8 Mon Sep 17 00:00:00 2001
From: Shuhao Zhang <594422141@qq.com>
Date: Sat, 17 Aug 2019 16:42:53 +0800
Subject: [PATCH] fold the code

---
 docs/misc/mo-algo.md | 824 ++++++++++++++++++++++++++-------------------------
 1 file changed, 415 insertions(+), 409 deletions(-)

diff --git a/docs/misc/mo-algo.md b/docs/misc/mo-algo.md
index 3d0ab964..65483690 100644
--- a/docs/misc/mo-algo.md
+++ b/docs/misc/mo-algo.md
@@ -116,50 +116,54 @@ $$
 
 算法总复杂度： $O(n\sqrt{n} )$ 
 
-下面的代码中 `mot` 表示答案的分母 (mother)， `sub` 表示分子， `sqn` 表示块的大小： $\sqrt{n}$ ， `arr` 是输入的数组， `node` 是存储询问的结构体， `tab` 是询问序列（排序后的）， `col` 同上所述。<strong >注意：下面代码中的移动区间的 4 个 for 循环的位置很关键，不能改变它们之间的位置关系，不然会 WA（因为有那个 `++l` 和 `--r` ）。</strong>代码：
-
-```cpp
-#include <bits/stdc++.h>
-#define bi(a) ((a - 1) / sqn + 1)
-using namespace std;
-typedef long long LL;
-template <typename tp>
-void read(tp& dig) {
-  char c = getchar();
-  dig = 0;
-  while (!isdigit(c)) c = getchar();
-  while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
-}
-struct node {
-  LL l, r, i;
-};
-LL n, m, sqn, arr[50005], l, r, ans, col[50005], sub[50005], mot[50005];
-vector<node> tab;
-bool cmp(node a, node b) {
-  if (bi(a.l) == bi(b.l)) return a.r < b.r;
-  return a.l < b.l;
-}
-LL gcd(LL a, LL b) { return !b ? a : gcd(b, a % b); }
-int main() {
-  read(n), read(m), sqn = sqrt(n);
-  for (LL i = 1; i <= n; i++) read(arr[i]);
-  for (LL i = 1, a, b; i <= m; i++)
-    read(a), read(b), tab.push_back((node){a, b, i});
-  sort(tab.begin(), tab.end(), cmp), l = r = tab[0].l, col[arr[l]]++;
-  for (LL i = 0, gcdnum; i < tab.size(); i++) {
-    for (; l < tab[i].l; l++) col[arr[l]]--, ans -= col[arr[l]];
-    for (--l; l >= tab[i].l; l--) ans += col[arr[l]], col[arr[l]]++;
-    for (; r > tab[i].r; r--) col[arr[r]]--, ans -= col[arr[r]];
-    for (++r; r <= tab[i].r; r++) ans += col[arr[r]], col[arr[r]]++;
-    sub[tab[i].i] = ans, l = tab[i].l, r = tab[i].r;
-    mot[tab[i].i] = ((r - l) * (r - l + 1)) >> 1;
-  }
-  for (LL i = 1, gcdn; i <= m; i++)
-    gcdn = gcd(sub[i], mot[i]),
-    printf("%lld/%lld\n", sub[i] / gcdn, mot[i] / gcdn);
-  return 0;
-}
-```
+下面的代码中 `mot` 表示答案的分母 (mother)， `sub` 表示分子， `sqn` 表示块的大小： $\sqrt{n}$ ， `arr` 是输入的数组， `node` 是存储询问的结构体， `tab` 是询问序列（排序后的）， `col` 同上所述。
+
+**注意：下面代码中的移动区间的 4 个 for 循环的位置很关键，不能改变它们之间的位置关系，不然会 WA（因为有那个 `++l` 和 `--r` ）。**
+
+??? 参考代码
+    
+    ```cpp
+    #include <bits/stdc++.h>
+    #define bi(a) ((a - 1) / sqn + 1)
+    using namespace std;
+    typedef long long LL;
+    template <typename tp>
+    void read(tp& dig) {
+      char c = getchar();
+      dig = 0;
+      while (!isdigit(c)) c = getchar();
+      while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
+    }
+    struct node {
+      LL l, r, i;
+    };
+    LL n, m, sqn, arr[50005], l, r, ans, col[50005], sub[50005], mot[50005];
+    vector<node> tab;
+    bool cmp(node a, node b) {
+      if (bi(a.l) == bi(b.l)) return a.r < b.r;
+      return a.l < b.l;
+    }
+    LL gcd(LL a, LL b) { return !b ? a : gcd(b, a % b); }
+    int main() {
+      read(n), read(m), sqn = sqrt(n);
+      for (LL i = 1; i <= n; i++) read(arr[i]);
+      for (LL i = 1, a, b; i <= m; i++)
+        read(a), read(b), tab.push_back((node){a, b, i});
+      sort(tab.begin(), tab.end(), cmp), l = r = tab[0].l, col[arr[l]]++;
+      for (LL i = 0, gcdnum; i < tab.size(); i++) {
+        for (; l < tab[i].l; l++) col[arr[l]]--, ans -= col[arr[l]];
+        for (--l; l >= tab[i].l; l--) ans += col[arr[l]], col[arr[l]]++;
+        for (; r > tab[i].r; r--) col[arr[r]]--, ans -= col[arr[r]];
+        for (++r; r <= tab[i].r; r++) ans += col[arr[r]], col[arr[r]]++;
+        sub[tab[i].i] = ans, l = tab[i].l, r = tab[i].r;
+        mot[tab[i].i] = ((r - l) * (r - l + 1)) >> 1;
+      }
+      for (LL i = 1, gcdn; i <= m; i++)
+        gcdn = gcd(sub[i], mot[i]),
+        printf("%lld/%lld\n", sub[i] / gcdn, mot[i] / gcdn);
+      return 0;
+    }
+    ```
 
 ## 普通莫队的优化
 
@@ -173,9 +177,9 @@ int main() {
 4 100
 ```
 
-手动模拟一下可以发现，r 指针的移动次数大概为 300 次，我们处理完第一个块之后， $l = 2, r = 100$ ，此时只需要移动两次 l 指针就可以得到第四个询问的答案，但是我们却将 r 指针移动到 1 来获取第三个询问的答案，再移动到 100 获取第四个询问的答案，这样多了九十几次的指针移动。我们怎么优化这个地方呢？这里我们就要用到奇偶化排序
+手动模拟一下可以发现，r 指针的移动次数大概为 300 次，我们处理完第一个块之后， $l = 2, r = 100$ ，此时只需要移动两次 l 指针就可以得到第四个询问的答案，但是我们却将 r 指针移动到 1 来获取第三个询问的答案，再移动到 100 获取第四个询问的答案，这样多了九十几次的指针移动。我们怎么优化这个地方呢？这里我们就要用到奇偶化排序。
 
-什么是奇偶化排序？奇偶化排序即对于属于奇数块的询问，r 按从小到大排序，对于属于偶数块的排序，r 从大到小排序，这样我们的 r 指针在处理完这个奇数块的问题后，将在返回的途中处理偶数块的问题，再向 n 移动处理下一个奇数块的问题，优化了 r 指针的移动次数，一般情况下，这种优化能让程序快 30% 左右
+什么是奇偶化排序？奇偶化排序即对于属于奇数块的询问，r 按从小到大排序，对于属于偶数块的排序，r 从大到小排序，这样我们的 r 指针在处理完这个奇数块的问题后，将在返回的途中处理偶数块的问题，再向 n 移动处理下一个奇数块的问题，优化了 r 指针的移动次数，一般情况下，这种优化能让程序快 30% 左右。
 
 排序代码：
 
@@ -252,12 +256,12 @@ struct node {
 
 ### 例题
 
-[数颜色 BZOJ - 2120](https://www.lydsy.com/JudgeOnline/problem.php?id=2120)
-
-题目大意：给你一个序列，M 个操作，有两种操作：
+!!! [数颜色 BZOJ - 2120](https://www.lydsy.com/JudgeOnline/problem.php?id=2120)
 
-1.  修改序列上某一位的数字
-2.  询问区间 $[l,r]$ 中数字的种类数（多个相同的数字只算一个）
+    题目大意：给你一个序列，M 个操作，有两种操作：
+    
+    1.  修改序列上某一位的数字
+    2.  询问区间 $[l,r]$ 中数字的种类数（多个相同的数字只算一个）
 
 我们不难发现，如果不带操作 1（修改）的话，我们就能轻松用普通莫队解决。
 
@@ -280,71 +284,71 @@ struct node {
 
 因此这道题就这样用带修改莫队轻松解决啦！
 
-代码：
-
-```cpp
-#include <bits/stdc++.h>
-#define SZ (10005)
-using namespace std;
-template <typename _Tp>
-inline void IN(_Tp& dig) {
-  char c;
-  dig = 0;
-  while (c = getchar(), !isdigit(c))
-    ;
-  while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
-}
-int n, m, sqn, c[SZ], ct[SZ], c1, c2, mem[SZ][3], ans, tot[1000005], nal[SZ];
-struct query {
-  int l, r, i, c;
-  bool operator<(const query another) const {
-    if (l / sqn == another.l / sqn) {
-      if (r / sqn == another.r / sqn) return i < another.i;
-      return r < another.r;
+??? 参考代码
+    
+    ```cpp
+    #include <bits/stdc++.h>
+    #define SZ (10005)
+    using namespace std;
+    template <typename _Tp>
+    inline void IN(_Tp& dig) {
+      char c;
+      dig = 0;
+      while (c = getchar(), !isdigit(c))
+        ;
+      while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
     }
-    return l < another.l;
-  }
-} Q[SZ];
-void add(int a) {
-  if (!tot[a]) ans++;
-  tot[a]++;
-}
-void del(int a) {
-  tot[a]--;
-  if (!tot[a]) ans--;
-}
-char opt[10];
-int main() {
-  IN(n), IN(m), sqn = pow(n, (double)2 / (double)3);
-  for (int i = 1; i <= n; i++) IN(c[i]), ct[i] = c[i];
-  for (int i = 1, a, b; i <= m; i++)
-    if (scanf("%s", opt), IN(a), IN(b), opt[0] == 'Q')
-      Q[c1].l = a, Q[c1].r = b, Q[c1].i = c1, Q[c1].c = c2, c1++;
-    else
-      mem[c2][0] = a, mem[c2][1] = ct[a], mem[c2][2] = ct[a] = b, c2++;
-  sort(Q, Q + c1), add(c[1]);
-  int l = 1, r = 1, lst = 0;
-  for (int i = 0; i < c1; i++) {
-    for (; lst < Q[i].c; lst++) {
-      if (l <= mem[lst][0] && mem[lst][0] <= r)
-        del(mem[lst][1]), add(mem[lst][2]);
-      c[mem[lst][0]] = mem[lst][2];
+    int n, m, sqn, c[SZ], ct[SZ], c1, c2, mem[SZ][3], ans, tot[1000005], nal[SZ];
+    struct query {
+      int l, r, i, c;
+      bool operator<(const query another) const {
+        if (l / sqn == another.l / sqn) {
+          if (r / sqn == another.r / sqn) return i < another.i;
+          return r < another.r;
+        }
+        return l < another.l;
+      }
+    } Q[SZ];
+    void add(int a) {
+      if (!tot[a]) ans++;
+      tot[a]++;
     }
-    for (; lst > Q[i].c; lst--) {
-      if (l <= mem[lst - 1][0] && mem[lst - 1][0] <= r)
-        del(mem[lst - 1][2]), add(mem[lst - 1][1]);
-      c[mem[lst - 1][0]] = mem[lst - 1][1];
+    void del(int a) {
+      tot[a]--;
+      if (!tot[a]) ans--;
     }
-    for (++r; r <= Q[i].r; r++) add(c[r]);
-    for (--r; r > Q[i].r; r--) del(c[r]);
-    for (--l; l >= Q[i].l; l--) add(c[l]);
-    for (++l; l < Q[i].l; l++) del(c[l]);
-    nal[Q[i].i] = ans;
-  }
-  for (int i = 0; i < c1; i++) printf("%d\n", nal[i]);
-  return 0;
-}
-```
+    char opt[10];
+    int main() {
+      IN(n), IN(m), sqn = pow(n, (double)2 / (double)3);
+      for (int i = 1; i <= n; i++) IN(c[i]), ct[i] = c[i];
+      for (int i = 1, a, b; i <= m; i++)
+        if (scanf("%s", opt), IN(a), IN(b), opt[0] == 'Q')
+          Q[c1].l = a, Q[c1].r = b, Q[c1].i = c1, Q[c1].c = c2, c1++;
+        else
+          mem[c2][0] = a, mem[c2][1] = ct[a], mem[c2][2] = ct[a] = b, c2++;
+      sort(Q, Q + c1), add(c[1]);
+      int l = 1, r = 1, lst = 0;
+      for (int i = 0; i < c1; i++) {
+        for (; lst < Q[i].c; lst++) {
+          if (l <= mem[lst][0] && mem[lst][0] <= r)
+            del(mem[lst][1]), add(mem[lst][2]);
+          c[mem[lst][0]] = mem[lst][2];
+        }
+        for (; lst > Q[i].c; lst--) {
+          if (l <= mem[lst - 1][0] && mem[lst - 1][0] <= r)
+            del(mem[lst - 1][2]), add(mem[lst - 1][1]);
+          c[mem[lst - 1][0]] = mem[lst - 1][1];
+        }
+        for (++r; r <= Q[i].r; r++) add(c[r]);
+        for (--r; r > Q[i].r; r--) del(c[r]);
+        for (--l; l >= Q[i].l; l--) add(c[l]);
+        for (++l; l < Q[i].l; l++) del(c[l]);
+        nal[Q[i].i] = ans;
+      }
+      for (int i = 0; i < c1; i++) printf("%d\n", nal[i]);
+      return 0;
+    }
+    ```
 
 ## 树上莫队
 
@@ -391,173 +395,173 @@ dfs 一棵树，然后如果 dfs 到 x 点，就 push_back(x),dfs 完 x 点，
 
 然后因为所包含的区间内可能没有 LCA，对于没有的情况要将多余的贡献删除，然后就完事了
 
-code：
-
-```cpp
-#include <algorithm>
-#include <cmath>
-#include <cstdio>
-#include <iostream>
-
-#define DEBUG printf("line:%d func:%s\n", __LINE__, __FUNCTION__);
-
-using namespace std;
-
-const int maxn = 200010;
-
-int f[maxn], g[maxn], id[maxn], head[maxn], cnt, last[maxn], dep[maxn],
-    fa[maxn][22], v[maxn], w[maxn];
-int block, index, n, m, q;
-int pos[maxn], col[maxn], app[maxn];
-bool vis[maxn];
-long long ans[maxn], cur;
-
-struct edge {
-  int to, nxt;
-} e[maxn];
-int cnt1 = 0, cnt2 = 0;  // 时间戳
-
-struct query {
-  int l, r, t, id;
-  bool operator<(const query &b) const {
-    return (pos[l] < pos[b.l]) || (pos[l] == pos[b.l] && pos[r] < pos[b.r]) ||
-           (pos[l] == pos[b.l] && pos[r] == pos[b.r] && t < b.t);
-  }
-} a[maxn], b[maxn];
-
-inline void addedge(int x, int y) {
-  e[++cnt] = (edge){y, head[x]};
-  head[x] = cnt;
-}
-
-void dfs(int x) {
-  id[f[x] = ++index] = x;
-  for (int i = head[x]; i; i = e[i].nxt) {
-    if (e[i].to != fa[x][0]) {
-      fa[e[i].to][0] = x;
-      dep[e[i].to] = dep[x] + 1;
-      dfs(e[i].to);
-    }
-  }
-  id[g[x] = ++index] = x;  // 括号序
-}
-
-inline void swap(int &x, int &y) {
-  int t;
-  t = x;
-  x = y;
-  y = t;
-}
-
-inline int lca(int x, int y) {
-  if (dep[x] < dep[y]) swap(x, y);
-  if (dep[x] != dep[y]) {
-    int dis = dep[x] - dep[y];
-    for (int i = 20; i >= 0; i--)
-      if (dis >= (1 << i)) dis -= 1 << i, x = fa[x][i];
-  }  // 爬到同一高度
-  if (x == y) return x;
-  for (int i = 20; i >= 0; i--) {
-    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
-  }
-  return fa[x][0];
-}
-
-inline void add(int x) {
-  if (vis[x])
-    cur -= (long long)v[col[x]] * w[app[col[x]]--];
-  else
-    cur += (long long)v[col[x]] * w[++app[col[x]]];
-  vis[x] ^= 1;
-}
-
-inline void modify(int x, int t) {
-  if (vis[x]) {
-    add(x);
-    col[x] = t;
-    add(x);
-  } else
-    col[x] = t;
-}  // 在时间维上移动
-
-int main() {
-  scanf("%d%d%d", &n, &m, &q);
-  for (int i = 1; i <= m; i++) scanf("%d", &v[i]);
-  for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
-  for (int i = 1; i < n; i++) {
-    int x, y;
-    scanf("%d%d", &x, &y);
-    addedge(x, y);
-    addedge(y, x);
-  }
-  for (int i = 1; i <= n; i++) {
-    scanf("%d", &last[i]);
-    col[i] = last[i];
-  }
-  dfs(1);
-  for (int j = 1; j <= 20; j++)
-    for (int i = 1; i <= n; i++)
-      fa[i][j] = fa[fa[i][j - 1]][j - 1];  // 预处理祖先
-  int block = pow(index, 2.0 / 3);
-  for (int i = 1; i <= index; i++) {
-    pos[i] = (i - 1) / block;
-  }
-  while (q--) {
-    int opt, x, y;
-    scanf("%d%d%d", &opt, &x, &y);
-    if (opt == 0) {
-      b[++cnt2].l = x;
-      b[cnt2].r = last[x];
-      last[x] = b[cnt2].t = y;
-    } else {
-      if (f[x] > f[y]) swap(x, y);
-      a[++cnt1] = (query){lca(x, y) == x ? f[x] : g[x], f[y], cnt2, cnt1};
-    }
-  }
-  sort(a + 1, a + cnt1 + 1);
-  int L, R, T;  // 指针坐标
-  L = R = 0;
-  T = 1;
-  for (int i = 1; i <= cnt1; i++) {
-    while (T <= a[i].t) {
-      modify(b[T].l, b[T].t);
-      T++;
+??? 参考代码
+    
+    ```cpp
+    #include <algorithm>
+    #include <cmath>
+    #include <cstdio>
+    #include <iostream>
+    
+    #define DEBUG printf("line:%d func:%s\n", __LINE__, __FUNCTION__);
+    
+    using namespace std;
+    
+    const int maxn = 200010;
+    
+    int f[maxn], g[maxn], id[maxn], head[maxn], cnt, last[maxn], dep[maxn],
+        fa[maxn][22], v[maxn], w[maxn];
+    int block, index, n, m, q;
+    int pos[maxn], col[maxn], app[maxn];
+    bool vis[maxn];
+    long long ans[maxn], cur;
+    
+    struct edge {
+      int to, nxt;
+    } e[maxn];
+    int cnt1 = 0, cnt2 = 0;  // 时间戳
+    
+    struct query {
+      int l, r, t, id;
+      bool operator<(const query &b) const {
+        return (pos[l] < pos[b.l]) || (pos[l] == pos[b.l] && pos[r] < pos[b.r]) ||
+               (pos[l] == pos[b.l] && pos[r] == pos[b.r] && t < b.t);
+      }
+    } a[maxn], b[maxn];
+    
+    inline void addedge(int x, int y) {
+      e[++cnt] = (edge){y, head[x]};
+      head[x] = cnt;
     }
-    while (T > a[i].t) {
-      modify(b[T].l, b[T].r);
-      T--;
+    
+    void dfs(int x) {
+      id[f[x] = ++index] = x;
+      for (int i = head[x]; i; i = e[i].nxt) {
+        if (e[i].to != fa[x][0]) {
+          fa[e[i].to][0] = x;
+          dep[e[i].to] = dep[x] + 1;
+          dfs(e[i].to);
+        }
+      }
+      id[g[x] = ++index] = x;  // 括号序
     }
-    while (L > a[i].l) {
-      L--;
-      add(id[L]);
+    
+    inline void swap(int &x, int &y) {
+      int t;
+      t = x;
+      x = y;
+      y = t;
     }
-    while (L < a[i].l) {
-      add(id[L]);
-      L++;
+    
+    inline int lca(int x, int y) {
+      if (dep[x] < dep[y]) swap(x, y);
+      if (dep[x] != dep[y]) {
+        int dis = dep[x] - dep[y];
+        for (int i = 20; i >= 0; i--)
+          if (dis >= (1 << i)) dis -= 1 << i, x = fa[x][i];
+      }  // 爬到同一高度
+      if (x == y) return x;
+      for (int i = 20; i >= 0; i--) {
+        if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
+      }
+      return fa[x][0];
     }
-    while (R > a[i].r) {
-      add(id[R]);
-      R--;
+    
+    inline void add(int x) {
+      if (vis[x])
+        cur -= (long long)v[col[x]] * w[app[col[x]]--];
+      else
+        cur += (long long)v[col[x]] * w[++app[col[x]]];
+      vis[x] ^= 1;
     }
-    while (R < a[i].r) {
-      R++;
-      add(id[R]);
+    
+    inline void modify(int x, int t) {
+      if (vis[x]) {
+        add(x);
+        col[x] = t;
+        add(x);
+      } else
+        col[x] = t;
+    }  // 在时间维上移动
+    
+    int main() {
+      scanf("%d%d%d", &n, &m, &q);
+      for (int i = 1; i <= m; i++) scanf("%d", &v[i]);
+      for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
+      for (int i = 1; i < n; i++) {
+        int x, y;
+        scanf("%d%d", &x, &y);
+        addedge(x, y);
+        addedge(y, x);
+      }
+      for (int i = 1; i <= n; i++) {
+        scanf("%d", &last[i]);
+        col[i] = last[i];
+      }
+      dfs(1);
+      for (int j = 1; j <= 20; j++)
+        for (int i = 1; i <= n; i++)
+          fa[i][j] = fa[fa[i][j - 1]][j - 1];  // 预处理祖先
+      int block = pow(index, 2.0 / 3);
+      for (int i = 1; i <= index; i++) {
+        pos[i] = (i - 1) / block;
+      }
+      while (q--) {
+        int opt, x, y;
+        scanf("%d%d%d", &opt, &x, &y);
+        if (opt == 0) {
+          b[++cnt2].l = x;
+          b[cnt2].r = last[x];
+          last[x] = b[cnt2].t = y;
+        } else {
+          if (f[x] > f[y]) swap(x, y);
+          a[++cnt1] = (query){lca(x, y) == x ? f[x] : g[x], f[y], cnt2, cnt1};
+        }
+      }
+      sort(a + 1, a + cnt1 + 1);
+      int L, R, T;  // 指针坐标
+      L = R = 0;
+      T = 1;
+      for (int i = 1; i <= cnt1; i++) {
+        while (T <= a[i].t) {
+          modify(b[T].l, b[T].t);
+          T++;
+        }
+        while (T > a[i].t) {
+          modify(b[T].l, b[T].r);
+          T--;
+        }
+        while (L > a[i].l) {
+          L--;
+          add(id[L]);
+        }
+        while (L < a[i].l) {
+          add(id[L]);
+          L++;
+        }
+        while (R > a[i].r) {
+          add(id[R]);
+          R--;
+        }
+        while (R < a[i].r) {
+          R++;
+          add(id[R]);
+        }
+        int x = id[L], y = id[R];
+        int llca = lca(x, y);
+        if (x != llca && y != llca) {
+          add(llca);
+          ans[a[i].id] = cur;
+          add(llca);
+        } else
+          ans[a[i].id] = cur;
+      }
+      for (int i = 1; i <= cnt1; i++) {
+        printf("%lld\n", ans[i]);
+      }
+      return 0;
     }
-    int x = id[L], y = id[R];
-    int llca = lca(x, y);
-    if (x != llca && y != llca) {
-      add(llca);
-      ans[a[i].id] = cur;
-      add(llca);
-    } else
-      ans[a[i].id] = cur;
-  }
-  for (int i = 1; i <= cnt1; i++) {
-    printf("%lld\n", ans[i]);
-  }
-  return 0;
-}
-```
+    ```
 
 ## 真·树上莫队
 
@@ -609,7 +613,7 @@ void move(int x, int y) {
 }
 ```
 
-对于求 LCA，我们可以用树剖，然后我们就可以把分块的步骤放到树剖的第一次 dfs 里面，时间戳也可以直接用第二次 dfs 的 dfs 序~~（如果你用 tarjan 就当我没说）~~
+对于求 LCA，我们可以用树剖，然后我们就可以把分块的步骤放到树剖的第一次 dfs 里面，时间戳也可以直接用第二次 dfs 的 dfs 序。
 
 ```cpp
 int bl[100002], bls = 0;  //属于的块，块的数量
@@ -657,140 +661,142 @@ if (!sta.empty()) {
 
 由于多了时间维，块的大小取到 0.6 的样子就差不多了
 
-```cpp
-#include <bits/stdc++.h>
-//#pragma GCC optimize(2)
-using namespace std;
-inline int gi() {
-  register int x, c, op = 1;
-  while (c = getchar(), c < '0' || c > '9')
-    if (c == '-') op = -op;
-  x = c ^ 48;
-  while (c = getchar(), c >= '0' && c <= '9')
-    x = (x << 3) + (x << 1) + (c ^ 48);
-  return x * op;
-}
-int head[100002], nxt[200004], ver[200004], tot = 0;
-void add(int x, int y) {
-  ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
-  ver[++tot] = x, nxt[tot] = head[y], head[y] = tot;
-}
-int bl[100002], bls = 0;
-unsigned step;
-int fa[100002], dp[100002], hs[100002] = {0}, sz[100002] = {0}, top[100002],
-                            id[100002];
-stack<int> sta;
-void dfs1(int x) {
-  sz[x] = 1;
-  unsigned ss = sta.size();
-  for (int i = head[x]; i; i = nxt[i])
-    if (ver[i] != fa[x]) {
-      fa[ver[i]] = x, dp[ver[i]] = dp[x] + 1;
-      dfs1(ver[i]);
-      sz[x] += sz[ver[i]];
-      if (sz[ver[i]] > sz[hs[x]]) hs[x] = ver[i];
-      if (sta.size() - ss >= step) {
+??? 参考代码
+    
+    ```cpp
+    #include <bits/stdc++.h>
+    //#pragma GCC optimize(2)
+    using namespace std;
+    inline int gi() {
+      register int x, c, op = 1;
+      while (c = getchar(), c < '0' || c > '9')
+        if (c == '-') op = -op;
+      x = c ^ 48;
+      while (c = getchar(), c >= '0' && c <= '9')
+        x = (x << 3) + (x << 1) + (c ^ 48);
+      return x * op;
+    }
+    int head[100002], nxt[200004], ver[200004], tot = 0;
+    void add(int x, int y) {
+      ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
+      ver[++tot] = x, nxt[tot] = head[y], head[y] = tot;
+    }
+    int bl[100002], bls = 0;
+    unsigned step;
+    int fa[100002], dp[100002], hs[100002] = {0}, sz[100002] = {0}, top[100002],
+                                id[100002];
+    stack<int> sta;
+    void dfs1(int x) {
+      sz[x] = 1;
+      unsigned ss = sta.size();
+      for (int i = head[x]; i; i = nxt[i])
+        if (ver[i] != fa[x]) {
+          fa[ver[i]] = x, dp[ver[i]] = dp[x] + 1;
+          dfs1(ver[i]);
+          sz[x] += sz[ver[i]];
+          if (sz[ver[i]] > sz[hs[x]]) hs[x] = ver[i];
+          if (sta.size() - ss >= step) {
+            bls++;
+            while (sta.size() != ss) bl[sta.top()] = bls, sta.pop();
+          }
+        }
+      sta.push(x);
+    }
+    int cnt = 0;
+    void dfs2(int x, int hf) {
+      top[x] = hf, id[x] = ++cnt;
+      if (!hs[x]) return;
+      dfs2(hs[x], hf);
+      for (int i = head[x]; i; i = nxt[i])
+        if (ver[i] != fa[x] && ver[i] != hs[x]) dfs2(ver[i], ver[i]);
+    }
+    int lca(int x, int y) {
+      while (top[x] != top[y]) {
+        if (dp[top[x]] < dp[top[y]]) swap(x, y);
+        x = fa[top[x]];
+      }
+      return dp[x] < dp[y] ? x : y;
+    }
+    struct qu {
+      int x, y, t, id;
+      bool operator<(const qu a) const {
+        return bl[x] == bl[a.x] ? (bl[y] == bl[a.y] ? t < a.t : bl[y] < bl[a.y])
+                                : bl[x] < bl[a.x];
+      }
+    } q[100001];
+    int qs = 0;
+    struct ch {
+      int x, y, b;
+    } upd[100001];
+    int ups = 0;
+    long long ans[100001];
+    int b[100001] = {0};
+    int a[100001];
+    long long w[100001];
+    long long v[100001];
+    long long now = 0;
+    bool vis[100001] = {0};
+    void back(int t) {
+      if (vis[upd[t].x]) {
+        now -= w[b[upd[t].y]--] * v[upd[t].y];
+        now += w[++b[upd[t].b]] * v[upd[t].b];
+      }
+      a[upd[t].x] = upd[t].b;
+    }
+    void change(int t) {
+      if (vis[upd[t].x]) {
+        now -= w[b[upd[t].b]--] * v[upd[t].b];
+        now += w[++b[upd[t].y]] * v[upd[t].y];
+      }
+      a[upd[t].x] = upd[t].y;
+    }
+    void update(int x) {
+      if (vis[x])
+        now -= w[b[a[x]]--] * v[a[x]];
+      else
+        now += w[++b[a[x]]] * v[a[x]];
+      vis[x] ^= 1;
+    }
+    void move(int x, int y) {
+      if (dp[x] < dp[y]) swap(x, y);
+      while (dp[x] > dp[y]) update(x), x = fa[x];
+      while (x != y) update(x), update(y), x = fa[x], y = fa[y];
+    }
+    int main() {
+      int n = gi(), m = gi(), k = gi();
+      step = (int)pow(n, 0.6);
+      for (int i = 1; i <= m; i++) v[i] = gi();
+      for (int i = 1; i <= n; i++) w[i] = gi();
+      for (int i = 1; i < n; i++) add(gi(), gi());
+      for (int i = 1; i <= n; i++) a[i] = gi();
+      for (int i = 1; i <= k; i++)
+        if (gi())
+          q[++qs].x = gi(), q[qs].y = gi(), q[qs].t = ups, q[qs].id = qs;
+        else
+          upd[++ups].x = gi(), upd[ups].y = gi();
+      for (int i = 1; i <= ups; i++) upd[i].b = a[upd[i].x], a[upd[i].x] = upd[i].y;
+      for (int i = ups; i; i--) back(i);
+      fa[1] = 1;
+      dfs1(1), dfs2(1, 1);
+      if (!sta.empty()) {
         bls++;
-        while (sta.size() != ss) bl[sta.top()] = bls, sta.pop();
+        while (!sta.empty()) bl[sta.top()] = bls, sta.pop();
+      }
+      for (int i = 1; i <= n; i++)
+        if (id[q[i].x] > id[q[i].y]) swap(q[i].x, q[i].y);
+      sort(q + 1, q + qs + 1);
+      int x = 1, y = 1, t = 0;
+      for (int i = 1; i <= qs; i++) {
+        if (x != q[i].x) move(x, q[i].x), x = q[i].x;
+        if (y != q[i].y) move(y, q[i].y), y = q[i].y;
+        int f = lca(x, y);
+        update(f);
+        while (t < q[i].t) change(++t);
+        while (t > q[i].t) back(t--);
+        ans[q[i].id] = now;
+        update(f);
       }
+      for (int i = 1; i <= qs; i++) printf("%lld\n", ans[i]);
+      return 0;
     }
-  sta.push(x);
-}
-int cnt = 0;
-void dfs2(int x, int hf) {
-  top[x] = hf, id[x] = ++cnt;
-  if (!hs[x]) return;
-  dfs2(hs[x], hf);
-  for (int i = head[x]; i; i = nxt[i])
-    if (ver[i] != fa[x] && ver[i] != hs[x]) dfs2(ver[i], ver[i]);
-}
-int lca(int x, int y) {
-  while (top[x] != top[y]) {
-    if (dp[top[x]] < dp[top[y]]) swap(x, y);
-    x = fa[top[x]];
-  }
-  return dp[x] < dp[y] ? x : y;
-}
-struct qu {
-  int x, y, t, id;
-  bool operator<(const qu a) const {
-    return bl[x] == bl[a.x] ? (bl[y] == bl[a.y] ? t < a.t : bl[y] < bl[a.y])
-                            : bl[x] < bl[a.x];
-  }
-} q[100001];
-int qs = 0;
-struct ch {
-  int x, y, b;
-} upd[100001];
-int ups = 0;
-long long ans[100001];
-int b[100001] = {0};
-int a[100001];
-long long w[100001];
-long long v[100001];
-long long now = 0;
-bool vis[100001] = {0};
-void back(int t) {
-  if (vis[upd[t].x]) {
-    now -= w[b[upd[t].y]--] * v[upd[t].y];
-    now += w[++b[upd[t].b]] * v[upd[t].b];
-  }
-  a[upd[t].x] = upd[t].b;
-}
-void change(int t) {
-  if (vis[upd[t].x]) {
-    now -= w[b[upd[t].b]--] * v[upd[t].b];
-    now += w[++b[upd[t].y]] * v[upd[t].y];
-  }
-  a[upd[t].x] = upd[t].y;
-}
-void update(int x) {
-  if (vis[x])
-    now -= w[b[a[x]]--] * v[a[x]];
-  else
-    now += w[++b[a[x]]] * v[a[x]];
-  vis[x] ^= 1;
-}
-void move(int x, int y) {
-  if (dp[x] < dp[y]) swap(x, y);
-  while (dp[x] > dp[y]) update(x), x = fa[x];
-  while (x != y) update(x), update(y), x = fa[x], y = fa[y];
-}
-int main() {
-  int n = gi(), m = gi(), k = gi();
-  step = (int)pow(n, 0.6);
-  for (int i = 1; i <= m; i++) v[i] = gi();
-  for (int i = 1; i <= n; i++) w[i] = gi();
-  for (int i = 1; i < n; i++) add(gi(), gi());
-  for (int i = 1; i <= n; i++) a[i] = gi();
-  for (int i = 1; i <= k; i++)
-    if (gi())
-      q[++qs].x = gi(), q[qs].y = gi(), q[qs].t = ups, q[qs].id = qs;
-    else
-      upd[++ups].x = gi(), upd[ups].y = gi();
-  for (int i = 1; i <= ups; i++) upd[i].b = a[upd[i].x], a[upd[i].x] = upd[i].y;
-  for (int i = ups; i; i--) back(i);
-  fa[1] = 1;
-  dfs1(1), dfs2(1, 1);
-  if (!sta.empty()) {
-    bls++;
-    while (!sta.empty()) bl[sta.top()] = bls, sta.pop();
-  }
-  for (int i = 1; i <= n; i++)
-    if (id[q[i].x] > id[q[i].y]) swap(q[i].x, q[i].y);
-  sort(q + 1, q + qs + 1);
-  int x = 1, y = 1, t = 0;
-  for (int i = 1; i <= qs; i++) {
-    if (x != q[i].x) move(x, q[i].x), x = q[i].x;
-    if (y != q[i].y) move(y, q[i].y), y = q[i].y;
-    int f = lca(x, y);
-    update(f);
-    while (t < q[i].t) change(++t);
-    while (t > q[i].t) back(t--);
-    ans[q[i].id] = now;
-    update(f);
-  }
-  for (int i = 1; i <= qs; i++) printf("%lld\n", ans[i]);
-  return 0;
-}
-```
+    ```
-- 
2.11.0