经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C++ » 查看文章
#8. 「模板」树链剖分
来源：cnblogs　　作者：AnRain安林　　时间：2024/8/26 10:10:35　　对本文有异议

题目传送门:#8. 「模板」树链剖分、

前置知识

  • 重链：重链（Heavy Path）是指树链剖分中的一条主要的路径，该路径上的节点数量较多，相邻节点之间的距离较近。轻链（Light Path）是指树链剖分中的其他路径，相邻节点之间的距离较远。

  • LCA：最近公共祖先

分析

上树状数组

首先，我们需要定义一个数组vals来存储每个节点的权值。然后，我们可以使用一个数组tree来表示树状数组，数组的下标表示节点的编号。对于节点i，其在tree数组中的下标为i，其父节点在tree数组中的下标为i+(i&-i)

然后只需要实现以下几个操作：

换根：将树的根节点设置为新根节点x。我们可以将所有节点的权值都减去vals[x]，然后再将vals[x]加到所有节点的权值中即可。
修改路径权值：给定两个节点u和v，将节点u到节点v的路径上的所有节点权值增加一个给定的值x。我们可以先将节点u的权值增加x，然后再将节点v的权值减去x。最后将tree数组中节点u到节点v的路径上的节点的值都增加x。
修改子树权值：给定一个节点x，将以节点x为根的子树内的所有节点权值增加一个给定的值y。我们可以将节点x的权值增加y，然后将tree数组中节点x及其所有子节点的值都增加y。
询问路径：给定两个节点u和v，询问节点u到节点v的路径上所有节点权值的和。我们可以先计算节点v到根节点的权值和，再计算节点u的权值，最后将两者相减即可。
询问子树：给定一个节点x，询问以节点x为根的子树内所有节点权值的和。我们可以直接返回tree数组中节点x及其所有子节点的值的和。

??ヽ(°▽°)ノ?

等等，还要上代码

Code

10分

  1. #include <cstdio>
  2. #define reg register
  3. int read() {
  4.     reg int s = 0, f = 1;
  5.     reg char ch;
  6.     for (; (ch = getchar()) < '0' || ch > '9'; ch == '-' ? f = -f : 0)
  7.         ;
  8.     for (; ch >= '0' && ch <= '9'; s = (s << 3) + (s << 1) + ch - 48, ch = getchar())
  9.         ;
  10.     return s * f;
  11. }
  12. const int N = 1e5 + 50;
  13. int next[N], to[N], first[N], tag[N << 2], tree[N << 2], val[N], cnt = 0, tot = 0, n, m;
  14. int dfn[N], son[N], size[N], efn[N], dep[N], top[N], fa[N], root, g[N];
  15. inline void push_up(int now) { tree[now] = tree[now << 1] + tree[now << 1 | 1]; }
  16. inline void add(int now, int l, int r, int v) {
  17.     tree[now] += (r - l + 1) * v;
  18.     tag[now] += v;
  19. }
  20. void push_down(int now, int l, int r) {
  21.     if (tag[now]) {
  22.         int mid = (l + r) >> 1;
  23.         add(now << 1, l, mid, tag[now]);
  24.         add(now << 1 | 1, mid + 1, r, tag[now]);
  25.         tag[now] = 0;
  26.     }
  27. }
  28. void _add(int u, int v) { next[++cnt] = first[u], first[u] = cnt, to[cnt] = v; }
  29. void build(int now, int l, int r) {
  30.     if (l == r) {
  31.         tree[now] = val[g[l]];
  32.         return;
  33.     }
  34.     int mid = (l + r) >> 1;
  35.     build(now << 1, l, mid);
  36.     build(now << 1 | 1, mid + 1, r);
  37.     push_up(now);
  38. }
  39. void mobify(int now, int l, int r, int L, int R, int v) {
  40.     if (L <= l && r <= R) {
  41.         add(now, l, r, v);
  42.         return;
  43.     }
  44.     int mid = (l + r) >> 1;
  45.     push_down(now, l, r);
  46.     if (L <= mid)
  47.         mobify(now << 1, l, mid, L, R, v);
  48.     if (R > mid)
  49.         mobify(now << 1 | 1, mid + 1, r, L, R, v);
  50.     push_up(now);
  51. }
  52. int query(int now, int l, int r, int L, int R) {
  53.     if (L <= l && r <= R)
  54.         return tree[now];
  55.     int mid = (l + r) >> 1, ans = 0;
  56.     push_down(now, l, r);
  57.     if (L <= mid)
  58.         ans += query(now << 1, l, mid, L, R);
  59.     if (R > mid)
  60.         ans += query(now << 1 | 1, mid + 1, r, L, R);
  61.     return ans;
  62. }
  63. void dfs0(int now) {
  64.     son[now] = 0;
  65.     size[now] = 1;
  66.     for (reg int i = first[now]; i; i = next[i])
  67.         if (!dep[to[i]]) {
  68.             fa[to[i]] = now;
  69.             dep[to[i]] = dep[now] + 1;
  70.             dfs0(to[i]);
  71.             size[now] += size[to[i]];
  72.             if (!son[now] || size[to[i]] > size[son[now]])
  73.                 son[now] = to[i];
  74.         }
  75. }
  76. void dfs1(int now, int t) {
  77.     dfn[now] = ++tot;
  78.     top[now] = t;
  79.     g[tot] = now;
  80.     if (son[now])
  81.         dfs1(son[now], t);
  82.     for (reg int i = first[now]; i; i = next[i])
  83.         if (!dfn[to[i]])
  84.             dfs1(to[i], to[i]);
  85.     efn[now] = tot;
  86. }
  87. int lca(int u, int v) {
  88.     while (top[u] != top[v]) (dep[top[u]] > dep[top[v]]) ? u = fa[top[u]] : v = fa[top[v]];
  89.     return (dep[u] < dep[v]) ? u : v;
  90. }
  91. void addpath(int u, int v, int k) {
  92.     while (top[u] != top[v])
  93.         (dep[top[u]] > dep[top[v]]) ? (mobify(1, 1, n, dfn[top[u]], dfn[u], k), u = fa[top[u]])
  94.                                     : (mobify(1, 1, n, dfn[top[v]], dfn[v], k), v = fa[top[v]]);
  95.     (dep[u] < dep[v]) ? mobify(1, 1, n, dfn[u], dfn[v], k) : mobify(1, 1, n, dfn[v], dfn[u], k);
  96. }
  97. void addtree(int u, int k) {
  98.     if (u == root) {
  99.         mobify(1, 1, n, 1, n, k);
  100.         return;
  101.     }
  102.     int g = lca(u, root);
  103.     if (g != u)
  104.         mobify(1, 1, n, dfn[u], efn[u], k);  // puts("wtf");
  105.     else {
  106.         // puts("wtm");
  107.         if (dfn[root] > 1)
  108.             mobify(1, 1, n, 1, dfn[root] - 1, k);
  109.         if (efn[root] < n)
  110.             mobify(1, 1, n, efn[root] + 1, n, k);
  111.         // mobify(1,1,n,1,dfn[u]-1,k);
  112.         // mobify(1,1,n,efn[u]+1,n,k);
  113.     }
  114. }
  115. void querypath(int u, int v) {
  116.     int ans = 0;
  117.     while (top[u] != top[v])
  118.         if (dep[top[u]] > dep[top[v]])
  119.             ans += query(1, 1, n, dfn[top[u]], dfn[u]), u = fa[top[u]];
  120.         else
  121.             ans += query(1, 1, n, dfn[top[v]], dfn[v]), v = fa[top[v]];
  122.     // printf("%d %d %d\n",u,v,ans);
  123.     ans += (dep[u] < dep[v]) ? query(1, 1, n, dfn[u], dfn[v]) : query(1, 1, n, dfn[v], dfn[u]);
  124.     printf("%d\n", ans);
  125. }
  126. void querytree(int u) {
  127.     if (u == root) {
  128.         printf("%d\n", tree[1]);
  129.         return;
  130.     }
  131.     int g = lca(u, root);
  132.     if (g != u)
  133.         printf("%d\n", query(1, 1, n, dfn[u], efn[u]));
  134.     else {
  135.         int ans = 0;
  136.         if (dfn[root] > 1)
  137.             ans += query(1, 1, n, 1, dfn[root] - 1);
  138.         if (efn[root] < n)
  139.             ans += query(1, 1, n, efn[root] + 1, n);
  140.         printf("%d\n", ans);
  141.     }
  142. }
  143. int main() {
  144.     n = read();
  145.     root = 1;
  146.     for (reg int i = 1; i <= n; i++) val[i] = read();
  147.     for (reg int u = 2, v; u <= n; u++) v = read(), _add(v, u);
  148.     m = read();
  149.     dep[1] = 1;
  150.     dfs0(1);
  151.     dfs1(1, 1);
  152.     build(1, 1, n);
  153.     for (reg int i = 1, opt, u, v, k; i <= m; i++) {
  154.         opt = read();
  155.         if (opt == 1)
  156.             root = read();
  157.         if (opt == 2)
  158.             u = read(), v = read(), k = read(), addpath(u, v, k);
  159.         if (opt == 3)
  160.             u = read(), k = read(), addtree(u, k);
  161.         if (opt == 4)
  162.             u = read(), v = read(), querypath(u, v);
  163.         if (opt == 5)
  164.             u = read(), querytree(u);
  165.     }
  166.     return 0;
  167. }

100分代码

  1. #include <bits/stdc++.h>
  2. #define INF 0x7fffffff
  3. #define ll long long
  4. using namespace std;
  6. ll read() {
  7.     ll k = 1, x = 0;
  8.     char ch = getchar();
  9.     while (ch < '0' || ch > '9') {
  10.         if (ch == '-')
  11.             k = -1;
  12.         ch = getchar();
  13.     }
  14.     while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - 48, ch = getchar();
  15.     return k * x;
  16. }
  18. const int N = 3e5 + 10;
  19. struct EDGE {
  20.     ll to, pre;
  21. } edge[N];
  22. ll a[N], size[N], fa[N], dep[N], id[N], w[N], son[N], top[N], head[N];
  23. ll cnt, n, m, r;
  25. //========== 关于换根的操作 =========
  26. inline ll find(ll u, ll v) {  //找从u(题目查询点的)到root第一个儿子
  27.     while (top[u] != top[v]) {
  28.         if (dep[top[u]] > dep[top[v]])
  29.             swap(u, v);  //保证u的深度更浅
  30.         if (fa[top[v]] == u)
  31.             return top[v];  //若链头的父亲恰好为u返回链头
  32.         v = fa[top[v]];     //不断向上跳
  33.     }
  34.     if (dep[u] > dep[v])
  35.         swap(u, v);
  36.     return son[u];
  37. }
  38. inline ll lca(ll u, ll v) {
  39.     while (top[u] != top[v]) {
  40.         if (dep[top[u]] > dep[top[v]])
  41.             swap(u, v);
  42.         v = fa[top[v]];
  43.     }
  44.     return dep[u] >= dep[v] ? v : u;
  45. }
  46. //==================================
  48. //================== 以下为线段树模板 ====================
  49. #define up(x) t[x].sum = t[x << 1].sum + t[x << 1 | 1].sum
  50. struct node {
  51.     ll l, r;
  52.     ll sum, lazy;
  53. } t[N << 2];
  54. ll len(ll p) { return t[p].r - t[p].l + 1; }
  55. void brush(ll p, ll k) {
  56.     t[p].lazy += k;
  57.     t[p].sum += len(p) * k;
  58. }
  59. void push_down(ll p) {
  60.     brush(p << 1, t[p].lazy);
  61.     brush(p << 1 | 1, t[p].lazy);
  62.     t[p].lazy = 0;
  63. }
  64. void build(ll p, ll l, ll r) {
  65.     t[p].l = l;
  66.     t[p].r = r;
  67.     if (l == r) {
  68.         t[p].sum = w[l];
  69.         return;
  70.     }
  71.     ll mid = l + r >> 1;
  72.     build(p << 1, l, mid);
  73.     build(p << 1 | 1, mid + 1, r);
  74.     up(p);
  75. }
  76. void update(ll p, ll l, ll r, ll k) {
  77.     if (t[p].l >= l && t[p].r <= r) {
  78.         brush(p, k);
  79.         return;
  80.     }
  81.     push_down(p);
  82.     ll mid = t[p].l + t[p].r >> 1;
  83.     if (mid >= l)
  84.         update(p << 1, l, r, k);
  85.     if (r >= mid + 1)
  86.         update(p << 1 | 1, l, r, k);
  87.     up(p);
  88. }
  89. ll getans(ll p, ll l, ll r) {
  90.     if (t[p].l >= l && t[p].r <= r)
  91.         return t[p].sum;
  92.     push_down(p);
  93.     ll ans = 0;
  94.     ll mid = t[p].l + t[p].r >> 1;
  95.     if (l <= mid)
  96.         ans += getans(p << 1, l, r);
  97.     if (r >= mid + 1)
  98.         ans += getans(p << 1 | 1, l, r);
  99.     return ans;
  100. }
  101. //================== 以上为线段树模板 ====================
  103. //================== 以下为树剖操作模板 ====================
  104. inline void updatetree(ll s, ll t, ll c) {  // s到t的简单路径加上c
  105.     while (top[s] != top[t]) {              //倍增思想，深度大的往上跳
  106.         if (dep[top[s]] > dep[top[t]])
  107.             swap(s, t);                   //默认t深度大
  108.         update(1, id[top[t]], id[t], c);  //先维护这一段链
  109.         t = fa[top[t]];                   //跳到这个链头的父节点，维护下一个链
  110.     }
  111.     if (dep[s] > dep[t])
  112.         swap(s, t);              //默认t深度大
  113.     update(1, id[s], id[t], c);  //维护s与现在t(同深度)的链
  114. }
  115. inline ll getanstree(ll s, ll t) {  //查询s到t的简单路径权值和
  116.     ll ans = 0;
  117.     while (top[s] != top[t]) {  //倍增思想，深度大的往上跳
  118.         if (dep[top[s]] > dep[top[t]])
  119.             swap(s, t);                       //默认t深度大
  120.         ans += getans(1, id[top[t]], id[t]);  //先查询这一段链
  121.         t = fa[top[t]];                       //跳到这个链头的父节点，查询下一个链
  122.     }
  123.     if (dep[s] > dep[t])
  124.         swap(s, t);                  //默认t深度大
  125.     ans += getans(1, id[s], id[t]);  //查询s与现在t(同深度)的链
  126.     return ans;
  127. }
  128. inline void updateson(ll x, ll t) {  //以x为根的子树加上t
  129.     if (x == r)
  130.         update(1, 1, n, t);  //当 x=root时，x就是此时整棵树的根，那么就是全局修改。
  131.     else {
  132.         ll LCA = lca(x, r);
  133.         if (LCA != x)  //若root不在x的子树中，正常修改
  134.             update(1, id[x], id[x] + size[x] - 1, t);
  135.         else {  //若在子树内，修改它到根的第一个儿子子树的补集
  136.             ll u = find(x, r);
  137.             update(1, 1, n, t);
  138.             update(1, id[u], id[u] + size[u] - 1, -t);
  139.         }
  140.     }
  141. }
  142. inline ll getansson(ll x) {  //以x为根的子树加上t
  143.     if (x == r)
  144.         return getans(1, 1, n);  //当 x=root时，x就是此时整棵树的根，那么就是全局查询。
  145.     else {
  146.         ll LCA = lca(x, r);
  147.         if (LCA != x)  //若root不在x的子树中，正常查询
  148.             return getans(1, id[x], id[x] + size[x] - 1);
  149.         else {  //若在子树内，查询它到根的第一个儿子子树的补集
  150.             ll u = find(x, r);
  151.             return getans(1, 1, n) - getans(1, id[u], id[u] + size[u] - 1);
  152.         }
  153.     }
  154. }
  155. //================== 以上为树剖操作模板 ====================
  157. //================== 以下为dfs ====================
  158. inline void dfs1(ll x, ll fath, ll deep) {  // x当前节点，f父亲，deep深度
  159.     dep[x] = deep;                          //标记每个点的深度
  160.     fa[x] = fath;                           //标记每个点的父亲
  161.     size[x] = 1;                            //标记每个非叶子节点的子树大小
  162.     ll maxson = -1;                         //记录重儿子的儿子数
  163.     for (ll i = head[x]; i; i = edge[i].pre) {
  164.         ll y = edge[i].to;
  165.         if (y == fath)
  166.             continue;
  167.         dfs1(y, x, deep + 1);
  168.         size[x] += size[y];      //把它的儿子数加到它身上
  169.         if (size[y] > maxson) {  //标记每个非叶子节点的重儿子编号
  170.             son[x] = y;
  171.             maxson = size[y];
  172.         }
  173.     }
  174. }
  176. ll tim;
  177. inline void dfs2(ll x, ll fst) {  // x当前节点，fst当前链的顶端
  178.     id[x] = ++tim;                //标记每个点dfs序
  179.     w[tim] = a[x];                //赋每个点的初始值
  180.     top[x] = fst;                 //标记这个点所在链的顶端
  181.     if (!son[x])
  182.         return;         //如果没有儿子则返回
  183.     dfs2(son[x], fst);  //按先处理重儿子
  184.     for (ll i = head[x]; i; i = edge[i].pre) {
  185.         ll y = edge[i].to;
  186.         if (y == fa[x] || y == son[x])
  187.             continue;
  188.         dfs2(y, y);  //轻儿子都有一条从它自己开始的链
  189.     }
  190. }
  191. //================== 以上为dfs ====================
  193. inline void add(ll u, ll v) {  //链式前向星
  194.     edge[++cnt].pre = head[u];
  195.     edge[cnt].to = v;
  196.     head[u] = cnt;
  197. }
  199. int main() {
  200.     n = read();
  201.     r = 1;
  202.     for (ll i = 1; i <= n; i++) a[i] = read();
  203.     for (ll i = 1; i < n; i++) {
  204.         ll a;
  205.         a = read();
  206.         add(a, i + 1), add(i + 1, a);
  207.     }
  209.     dfs1(r, 0, 1);
  210.     dfs2(r, r);
  211.     build(1, 1, n);
  212.     m = read();
  213.     for (ll i = 1; i <= m; i++) {
  214.         ll opt = read(), x = read();
  215.         if (opt == 1)
  216.             r = x;
  217.         if (opt == 2) {
  218.             ll y = read(), z = read();
  219.             updatetree(x, y, z);
  220.         }
  221.         if (opt == 4) {
  222.             ll y = read();
  223.             cout << getanstree(x, y) << endl;
  224.         }
  225.         if (opt == 3) {
  226.             ll z = read();
  227.             updateson(x, z);
  228.         }
  229.         if (opt == 5)
  230.             cout << getansson(x) << endl;
  231.     }
  232.     return 0;
  233. }

原文链接：https://www.cnblogs.com/yhy2013/p/18380155

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C++热门文章

  • C/C++编程笔记：编写不会在C ++中编译的C程序，我教你呀！
  • 洛谷 P2085 最小函数值
  • 使用C++界面框架ImGUI开发一个简单程序
  • C++ Json解析CJsonObject的详细使用
  • C++编译错误杂记
  • 二分法（二）：采用二分法解决“最小化最大值问题”
  • C++实现json字符串与map的转换
  • C++借助curses库实现俄罗斯方块
  • 长乐培训Day5
  • 【OpenFOAM】——OpenFOAM入门算例学习

    • C++推荐文章

  • #8. 「模板」树链剖分
  • 预设型 DP
  • Standard Template Libary or C++ Standard Library
  • 一种优秀的虚拟机内存架构 - AQ
  • 如何让 MGR 不从 Primary 节点克隆数据？
  • TLScanary：Pwn中的利器
  • c++临时对象导致的生命周期问题
  • C++(Qt)-GIS开发-简易瓦片地图下载器
  • 逆向通达信 x 逆向微信 x 逆向Qt
  • C++面向对象

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号