树链剖分（LOJ-139）

更佳的阅读体验http://ddoss.top/index.php/2020/03/10/loj-139/

给定一棵  个节点的树，初始时该树的根为  号节点，每个节点有一个给定的权值。下面依次进行  个操作，操作分为如下五种类型：

• 换根：将一个指定的节点设置为树的新根。
• 修改路径权值：给定两个节点，将这两个节点间路径上的所有节点权值（含这两个节点）增加一个给定的值。
• 修改子树权值：给定一个节点，将以该节点为根的子树内的所有节点权值增加一个给定的值。
• 询问路径：询问某条路径上节点的权值和。
• 询问子树：询问某个子树内节点的权值和。

主要的思路就是处理出重链和轻链，利用dfs序求出每条重链连续的id，利用线段树进行区间修改和查询。

前置知识点线段树，lca，差分，dfs序

树链剖分代码量还是比较大的，， 下面就直接放代码了 。

 

  1 /** 
  2  * KUANGBIN___LOJ_139_TCS2_CPP
  3  * @author : MWT 
  4  *
  5  */
  6 
  7 #include <iostream>
  8 #include <cstdio>
  9 #include <cmath>
 10 #include <cstring>
 11 #include <climits>
 12 #include <queue>
 13 #include <vector>
 14 #include <stack>
 15 #include <algorithm>
 16 #include <cctype>
 17 
 18 #define FAST_IO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
 19 #define sca(a) scanf("%d",&a);
 20 #define sca2(a, b) scanf("%d%d",&a,&b)
 21 #define sca3(a, b, c) scanf("%d%d%d",&a,&b,&c)
 22 #define scac(a) scanf("%c",a);
 23 #define scacc(a, b) scanf("%c%c",a,b)
 24 #define mem(a, b) memset(a,b,sizeof(a))
 25 #define lson(x) x << 1
 26 #define rson(x) x << 1 | 1
 27 #define int long long
 28 using namespace std;
 29 template<class T>void tomax(T &a, T b) { a = max(a, b); }
 30 template<class T>void tomin(T &a, T b) { a = min(a, b); }
 31 
 32 typedef long long ll;
 33 typedef pair<int, int> pii;
 34 
 35 using namespace std;
 36 
 37 const int maxn = 200020;
 38 struct edge {
 39     int to, nxt;
 40 } e[maxn << 1];
 41 struct point {
 42     int val, add;
 43 } p[maxn << 2];
 44 int head[maxn], a[maxn], b[maxn];
 45 int par[maxn], dep[maxn], top[maxn], id[maxn], size[maxn], son[maxn];
 46 int n, q, root, cnt, ncnt;
 47 namespace segment_tree {
 48     void build(int x, int stdl, int stdr) {
 49         p[x].add = 0;
 50         if (stdl == stdr) {
 51             p[x].val = a[stdl];
 52             return;
 53         }
 54         int mid = stdl + stdr >> 1;
 55         build(lson(x), stdl, mid), build(rson(x), mid + 1, stdr);
 56         p[x].val = p[lson(x)].val + p[rson(x)].val;
 57     }
 58     void pushdown(int x, int stdl, int stdr) {
 59         int mid = stdl + stdr >> 1;
 60         p[lson(x)].val += (mid - stdl + 1) * p[x].add;
 61         p[rson(x)].val += (stdr - mid) * p[x].add;
 62         p[lson(x)].add += p[x].add;
 63         p[rson(x)].add += p[x].add;
 64         p[x].add = 0;
 65     }
 66     void update_add(int x, int stdl, int stdr, int l, int r, int k) {
 67         if (r < stdl || stdr < l)
 68             return;
 69         if (l <= stdl && stdr <= r) {
 70             p[x].val += k * (stdr - stdl + 1), p[x].add += k;
 71             return;
 72         }
 73         pushdown(x, stdl, stdr);
 74         int mid = stdl + stdr >> 1;
 75         update_add(lson(x), stdl, mid, l, r, k);
 76         update_add(rson(x), mid + 1, stdr, l, r, k);
 77         p[x].val = p[lson(x)].val + p[rson(x)].val;
 78     }
 79     int query(int x, int stdl, int stdr, int l, int r) {
 80         if (r < stdl || stdr < l)
 81             return 0;
 82         if (l <= stdl && stdr <= r)
 83             return p[x].val;
 84         pushdown(x, stdl, stdr);
 85         int mid = stdl + stdr >> 1;
 86         return query(lson(x), stdl, mid, l, r) + query(rson(x), mid + 1, stdr, l, r);
 87     }
 88 }  // namespace segment_tree
 89 using namespace segment_tree;
 90 namespace mwt {
 91     void add(int x, int y) {
 92         e[++cnt].to = y;
 93         e[cnt].nxt = head[x];
 94         head[x] = cnt;
 95     }
 96     void dfs1(int x) {
 97         size[x] = 1;
 98         dep[x] = dep[par[x]] + 1;
 99         for (int i = head[x]; i; i = e[i].nxt) {
100             int t = e[i].to;
101             if (t == par[x])
102                 continue;
103             par[t] = x;
104             dfs1(t);
105             size[x] += size[t];
106             if (!son[x] || size[son[x]] < size[t])
107                 son[x] = t;
108         }
109     }
110     void dfs2(int x, int y) {
111         top[x] = y;
112         id[x] = ++ncnt, a[ncnt] = b[x];
113         if (son[x])
114             dfs2(son[x], y);
115         for (int i = head[x]; i; i = e[i].nxt) {
116             int t = e[i].to;
117             if (t == par[x] || t == son[x])
118                 continue;
119             dfs2(t, t);
120         }
121     }
122     int lca(int x, int y) {
123         while (top[x] != top[y]) {
124             if (dep[top[x]] < dep[top[y]])
125                 swap(x, y);
126             x = par[top[x]];
127         }
128         if (dep[x] > dep[y])
129             swap(x, y);
130         return x;
131     }
132     int findson(int x, int y) {
133         while (top[x] != top[y]) {
134             if (par[top[y]] == x)
135                 return top[y];
136             y = par[top[y]];
137         }
138         return son[x];
139     }
140 }  // namespace mwt
141 using namespace mwt;
142 namespace solve_all {
143     void update_path(int x, int y, int val) {
144         while (top[x] != top[y]) {
145             if (dep[top[x]] < dep[top[y]])
146                 swap(x, y);
147             update_add(1, 1, n, id[top[x]], id[x], val);
148             x = par[top[x]];
149         }
150         if (dep[x] > dep[y])
151             swap(x, y);
152         update_add(1, 1, n, id[x], id[y], val);
153     }
154     void update_subtree(int x, int val) {
155         if (lca(x, root) != x)
156             update_add(1, 1, n, id[x], id[x] + size[x] - 1, val);
157         else if (x == root)
158             update_add(1, 1, n, 1, n, val);
159         else {
160             int s = findson(x, root);
161             update_add(1, 1, n, 1, id[s] - 1, val);
162             if (id[s] + size[s] <= n)
163                 update_add(1, 1, n, id[s] + size[s], n, val);
164         }
165     }
166     int query_path(int x, int y) {
167         int ans = 0;
168         while (top[x] != top[y]) {
169             if (dep[top[x]] < dep[top[y]])
170                 swap(x, y);
171             ans += query(1, 1, n, id[top[x]], id[x]);
172             x = par[top[x]];
173         }
174         if (dep[x] > dep[y])
175             swap(x, y);
176         ans += query(1, 1, n, id[x], id[y]);
177         return ans;
178     }
179     int query_subtree(int x) {
180         if (lca(x, root) != x)
181             return query(1, 1, n, id[x], id[x] + size[x] - 1);
182         else if (x == root)
183             return query(1, 1, n, 1, n);
184         else {
185             int s = findson(x, root), ans = 0;
186             ans += query(1, 1, n, 1, id[s] - 1);
187             if (id[s] + size[s] <= n)
188                 ans += query(1, 1, n, id[s] + size[s], n);
189             return ans;
190         }
191     }
192 }  // namespace solve_all
193 using namespace solve_all;
194 
195 
196 signed main() {
197     scanf("%lld", &n);
198     for (int i = 1; i <= n; i++) scanf("%lld", &b[i]);
199     for (int i = 2; i <= n; i++) {
200         int x;
201         scanf("%lld", &x);
202         add(x, i), add(i, x);
203     }
204     dfs1(1), dfs2(1, 1), build(1, 1, n);
205     scanf("%lld", &q);
206     while (q--) {
207         int opt, x, y, z;
208         scanf("%lld", &opt);
209         if (opt == 1)
210             scanf("%lld", &root);
211         if (opt == 2)
212             scanf("%lld%lld%lld", &x, &y, &z), update_path(x, y, z);
213         if (opt == 3)
214             scanf("%lld%lld", &x, &y), update_subtree(x, y);
215         if (opt == 4)
216             scanf("%lld%lld", &x, &y), printf("%lld\n", query_path(x, y));
217         if (opt == 5)
218             scanf("%lld", &x), printf("%lld\n", query_subtree(x));
219     }
220     return 0;
221 }

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄

×

选择打赏方式：

微信 QQ钱包 支付宝

打赏

打赏

打赏

多少都是心意！谢谢大家！！！