[关闭]
@WangYixu 2018-06-19T12:56:54.000000Z 字数 4822 阅读 943

树链剖分

OI 算法 笔记 树剖 线段树

为什么要树链剖分？

因为有些sb棒极了的出题人，一想到某个操作满足可加性，就开始考各种数据结构来维护这个操作，其中一种考法就是在一棵树上，每个点都有权值，来维护这棵树上的某个链或子树的权值“和”，还要支持什么子树修改啊，链修改啊之类的蛋疼必要操作，为了卡过出题人的毒瘤数据提高我们算法的效率，我们引入树链剖分这一操作。

什么是树链剖分？

这里用加法代表那些满足可加性的操作（还有乘法、异或等等）。

树链剖分，就是将一棵树剖分成几条链，变成线性结构，然后就可以跑各种线段树维护了。

为了让树上的链在线性结构上尽量分成较少的链，我们引入树链剖分的关键——轻与重：

上图：

怎么树链剖分？

Step 1 dfs

这一步，我们要对树进行dfs，来确定一下几个内容：

code:

  1. LL w[N], son[N], fa[N], dep[N];
  2. il LL dfs(LL x, LL f, LL deep) {
  3.     sz[x] = 1;
  4.     dep[x] = deep;
  5.     fa[x] = f;
  6.     for (register int i = hd[x]; i; i = nxt[i]) if (to[i] != f) {
  7.         sz[x] += dfs(to[i], x, deep + 1);
  8.         if (sz[to[i]] > sz[son[x]]) son[x] = to[i];
  9.     }
  10.     return sz[x];
  11. }

Step 2 rebuild

然后，我们对树进行重建，进行树链剖分，在这一步，我们要完成：

这里，我们要先处理重儿子，再处理轻儿子，这样就能保证每条重链一定在线性结构中连续，而重链又足够长，查询次数可以得到有效降低。

code:

  1. LL wt[N], id[N], sz[N], top[N], ncnt;
  2. il void Rebuild(LL x, LL f) { // f is current 'top'
  3.     id[x] = ++ncnt;
  4.     wt[ncnt] = w[x];
  5.     top[x] = f;
  6.     if (!son[x]) return;
  7.     Rebuild(son[x], f);
  8.     for (register int i = hd[x]; i; i = nxt[i]) {
  9.         if (to[i] != fa[x] && to[i] != son[x]) {
  10.             Rebuild(to[i], to[i]);
  11.         }
  12.     }
  13. }

Step 3 Change & Query

接下来就是修改和查询了，一个一个的讲:

1.链修改

给定一条链的左右端点x,y，将链上的每个节点增加某个值val
设更深的点为x，修改x到重链的顶端的权值。然后令x跳到顶端的父亲节点，重复这一过程，直至x, y在同一条重链中，这时，直接修改区间即可。
code:

  1. // Add is a funcition in SegmentTree, 
  2. // it can fast add a value to a segment
  3. il void Achain(LL x, LL y, LL val) {
  4.     val %= p;
  5.     while (top[x] != top[y]) {
  6.         if (dep[top[x]] < dep[top[y]]) swap(x, y);
  7.         Add(1, 1, n, id[top[x]], id[x], val);
  8.         x = fa[top[x]];
  9.     }
  10.     if (id[x] > id[y]) swap(x, y);
  11.     Add(1, 1, n, id[x], id[y], val);
  12. }

2.链查询

给定一条链的左右端点x,y，返回链上的每个节点的权值和。
做法类似于修改。
code:

  1. // Sum is a funcition in SegmentTree, 
  2. // it can fast return the sum of a segment
  3. il LL Qchain(LL x, LL y) {
  4.     LL ans = 0;
  5.     while (top[x] != top[y]) {
  6.         if (dep[top[x]] < dep[top[y]]) swap(x, y);
  7.         ans = (ans + Sum(1, 1, n, id[top[x]], id[x])) % p;
  8.         x = fa[top[x]];
  9.     }
  10.     if (id[x] > id[y]) swap(x, y);
  11.     ans = (ans + Sum(1, 1, n, id[x], id[y])) % p;
  12.     printf("%lld\n", ans);
  13. }

3.子树修改与查询

使某个点及其子树的权值增加val。
由于一棵子树在线性结构是连续的，直接对区间操作即可。
code:

  1. il void Ason(LL rt, LL val) {
  2.     Add(1, 1, n, id[rt], id[rt] + sz[rt] - 1, val % p);
  3. }
  5. il LL Qson(LL rt) {
  6.     printf("%d\n", Sum(1, 1, n, id[rt], id[rt] + sz[rt] - 1) % p);
  7. }

模板：LgP3384

codes:

  1. #include<cctype>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using std::swap;
  6. #define il inline
  7. typedef long long LL;
  8. const int N = 100000 + 10;
  9. const int M = (N - 1) * 2 + 10;
  11. LL hd[N], to[M], nxt[M], cnt; // Tree
  12. LL w[N], son[N], fa[N], dep[N]; // Basic Info 
  13. LL wt[N], id[N], sz[N], top[N], ncnt; // Tree Chain Split
  14. LL st[N << 2], add[N << 2]; // Segment Tree
  15. LL n, m, r, p; // Prob Info
  17. //---SegmentTree---//
  18. il LL ls(LL x) { return x << 1; }
  19. il LL rs(LL x) { return (x << 1) | 1; }
  21. il void PushDown(LL rt, LL len) {
  22.     if (!add[rt]) return;
  23.     (st[ls(rt)] += add[rt] * (len - (len >> 1)) % p) %= p;
  24.     (st[rs(rt)] += add[rt] * (len >> 1) % p) %= p;
  25.     (add[ls(rt)] += add[rt]) %= p;
  26.     (add[rs(rt)] += add[rt]) %= p;
  27.     add[rt] = 0;
  28. }
  30. il void Build(LL rt, LL l, LL r) {
  31.     if (l == r) { st[rt] = wt[l]; return; }
  32.     LL mid = (l + r) >> 1;
  33.     Build(ls(rt), l, mid);
  34.     Build(rs(rt), mid + 1, r);
  35.     st[rt] = st[ls(rt)] + st[rs(rt)];
  36. }
  38. il void Add(LL rt, LL l, LL r, LL ql, LL qr, LL val) {
  39.     if (ql <= l && qr >= r) {
  40.         add[rt] = (add[rt] + val) % p;
  41.         st[rt] = (st[rt] + (r - l + 1) * val) % p;
  42.         return;
  43.     }
  44.     PushDown(rt, r - l + 1);
  45.     LL mid = (l + r) >> 1;
  46.     if (ql <= mid) Add(ls(rt), l, mid, ql, qr, val);
  47.     if (qr > mid) Add(rs(rt), mid + 1, r, ql, qr, val);
  48.     st[rt] = (st[ls(rt)] + st[rs(rt)]) % p;
  49. }
  51. il LL Sum(LL rt, LL l, LL r, LL ql, LL qr) {
  52.     if (ql <= l && qr >= r) {
  53.         return st[rt] % p;
  54.     }
  55.     PushDown(rt, r - l + 1);
  56.     LL mid = (l + r) >> 1, ans = 0;
  57.     if (ql <= mid) ans = (ans + Sum(ls(rt), l, mid, ql, qr)) % p;
  58.     if (qr > mid) ans = (ans + Sum(rs(rt), mid + 1, r, ql, qr)) % p;
  59.     return ans;
  60. }
  61. //---End---//
  63. //---树链剖分---//
  64. il LL dfs(LL x, LL f, LL deep) {
  65.     sz[x] = 1;
  66.     dep[x] = deep;
  67.     fa[x] = f;
  68.     for (register int i = hd[x]; i; i = nxt[i]) if (to[i] != f) {
  69.         sz[x] += dfs(to[i], x, deep + 1);
  70.         if (sz[to[i]] > sz[son[x]]) son[x] = to[i];
  71.     }
  72.     return sz[x];
  73. }
  75. il void Rebuild(LL x, LL f) {
  76.     id[x] = ++ncnt;
  77.     wt[ncnt] = w[x];
  78.     top[x] = f;
  79.     if (!son[x]) return;
  80.     Rebuild(son[x], f);
  81.     for (register int i = hd[x]; i; i = nxt[i]) {
  82.         if (to[i] != fa[x] && to[i] != son[x]) {
  83.             Rebuild(to[i], to[i]);
  84.         }
  85.     }
  86. }
  88. il void Achain(LL x, LL y, LL val) {
  89.     val %= p;
  90.     while (top[x] != top[y]) {
  91.         if (dep[top[x]] < dep[top[y]]) swap(x, y);
  92.         Add(1, 1, n, id[top[x]], id[x], val);
  93.         x = fa[top[x]];
  94.     }
  95.     if (id[x] > id[y]) swap(x, y);
  96.     Add(1, 1, n, id[x], id[y], val);
  97. }
  99. il LL Qchain(LL x, LL y) {
  100.     LL ans = 0;
  101.     while (top[x] != top[y]) {
  102.         if (dep[top[x]] < dep[top[y]]) swap(x, y);
  103.         ans = (ans + Sum(1, 1, n, id[top[x]], id[x])) % p;
  104.         x = fa[top[x]];
  105.     }
  106.     if (id[x] > id[y]) swap(x, y);
  107.     ans = (ans + Sum(1, 1, n, id[x], id[y])) % p;
  108.     printf("%lld\n", ans);
  109. }
  111. il void Ason(LL rt, LL val) {
  112.     Add(1, 1, n, id[rt], id[rt] + sz[rt] - 1, val % p);
  113. }
  115. il LL Qson(LL rt) {
  116.     printf("%d\n", Sum(1, 1, n, id[rt], id[rt] + sz[rt] - 1) % p);
  117. }
  118. //---End---// 
  120. //---BasicOperate---//
  121. char c; LL tmp;
  122. il LL read() {
  123.     while (!isdigit(c = getchar()));
  124.     tmp = c ^ '0';
  125.     while (isdigit(c = getchar())) tmp = (tmp << 3) + (tmp << 1) + (c ^ '0');
  126.     return tmp;
  127. }
  129. il void adde(int x, int y) {
  130.     cnt++;
  131.     to[cnt] = y;
  132.     nxt[cnt] = hd[x];
  133.     hd[x] = cnt;
  134. }
  135. //---End---//
  137. int main() {
  138.     n = read(); m = read(); r = read(); p = read();
  139.     for (register int i = 1; i <= n; ++i) w[i] = read();
  140.     for (register int i = 1, x, y; i < n; ++i) {
  141.         x = read(); y = read();
  142.         adde(x, y); adde(y, x);
  143.     } 
  145.     dfs(r, 0, 1);
  146.     Rebuild(r, r);
  147.     Build(1, 1, n);
  149.     for (register int i = 1, x, y, z, op; i <= m; ++i) {
  150.         op = read();
  151.         switch(op) {
  152.             case 1 : 
  153.                 x = read(); y = read(); z = read();
  154.                 Achain(x, y, z);
  155.                 break;
  156.             case 2 :
  157.                 x = read(); y = read();
  158.                 Qchain(x, y);
  159.                 break;
  160.             case 3 : 
  161.                 x = read(); z = read();
  162.                 Ason(x, z);
  163.                 break;
  164.             case 4 :
  165.                 x = read();
  166.                 Qson(x);
  167.                 break;
  168.         }
  169.     }
  170.     return 0;
  171. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注