感觉这已经不能说是模板了吧......
解析：
难点在于换根后对子树进行的操作，设rt为当前根节点，u为操作子树：
u=rt时，就是对整棵树操作，没事么好说的。
rt不在u的子树范围内，操作对象就是u的子树。
rt在u的子树范围内，操作范围就是整棵树减去u-rt路径上深度最小的点（可以用线段树维护该点）的子树（不包括u）。
（可以画图模拟一下，注意这里我所说的某个节点的子树都是以1为根的情况）。
代码：
1 #include <bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 const int N = 1e5 + 10, inf = 1e9;
5 int head[N], to[N << 1], nxt[N << 1], tot;
6 int n, m, cnt, rt = 1;
7 ll val[N];
8 int dep[N], size[N], top[N], fa[N], son[N], id[N], rev[N];
9 int opt, a, b, c;
10 struct node {
11 int minp;
12 ll sum, lazy;
13 }t[N << 2];
14 void add(int a, int b) {
15 nxt[++ tot] = head[a], head[a] = tot, to[tot] = b;
16 }
17 void dfs1(int u, int f) {
18 size[u] = 1;
19 for (int i = head[u]; i; i = nxt[i]) {
20 int v = to[i];
21 if (v == f) continue;
22 fa[v] = u;
23 dep[v] = dep[u] + 1;
24 dfs1(v, u);
25 size[u] += size[v];
26 if (size[v] > size[son[u]]) son[u] = v;
27 }
28 }
29 void dfs2(int u, int t) {
30 top[u] = t;
31 id[u] = ++ cnt;
32 rev[cnt] = u;
33 if(!son[u]) return ;
34 dfs2(son[u], t);
35 for (int i = head[u]; i; i = nxt[i]) {
36 int v = to[i];
37 if (v != fa[u] && v != son[u]) dfs2(v, v);
38 }
39 }
40 namespace SegmentTree {
41 #define mid ((l + r) >> 1)
42 #define lson k << 1, l, mid
43 #define rson k << 1 | 1, mid + 1, r
44 int tmin(int a, int b) {//返回深度更小的点
45 if (a == inf) return b;
46 if (b == inf) return a;
47 if (dep[a] < dep[b]) return a;
48 else return b;
49 }
50 void pushup(int k) {//更新信息
51 t[k].sum = t[k << 1].sum + t[k << 1 | 1].sum;
52 t[k].minp = tmin(t[k << 1].minp, t[k << 1 | 1].minp);
53 }
54 void pushdown(int k, int l, int r) {//标记下传
55 if (!t[k].lazy) return ;
56 t[k << 1].lazy += t[k].lazy;
57 t[k << 1 | 1].lazy += t[k].lazy;
58 t[k << 1].sum += (mid - l + 1) * t[k].lazy;
59 t[k << 1 | 1].sum += (r - mid) * t[k].lazy;
60 t[k].lazy = 0;
61 }
62 void build(int k, int l, int r) {//建树
63 if (l == r) {
64 t[k].minp = rev[l];
65 t[k].sum = val[rev[l]];
66 return ;
67 }
68 build(lson), build(rson);
69 pushup(k);
70 }
71 void update(int k, int l, int r, int L, int R, ll v) {//更新权值
72 if (L <= l && R >= r) {
73 t[k].sum += (r - l + 1) * v;
74 t[k].lazy += v;
75 return ;
76 }
77 pushdown(k, l, r);
78 if (L <= mid) update(lson, L, R, v);
79 if (R > mid) update(rson, L, R, v);
80 pushup(k);
81 }
82 ll query(int k, int l, int r, int L, int R) {
83 ll ans = 0;
84 if (L <= l && R >= r) return t[k].sum;
85 pushdown(k, l, r);
86 if (L <= mid) ans += query(lson, L, R);
87 if (R > mid) ans += query(rson, L, R);
88 return ans;
89 }
90 int find(int k, int l, int r, int L, int R) {
91 int x = inf;
92 if (R < L) return inf;
93 if (L <= l && R >= r) return t[k].minp;//返回树中节点编号
94 if (L <= mid) x = tmin(x, find(lson, L, R));
95 if (R > mid) x = tmin(x, find(rson, L, R));
96 return x;
97 }
98 int lca(int a, int b) {
99 while (top[a] != top[b]) {
100 if (dep[top[a]] < dep[top[b]]) swap(a, b);
101 a = fa[top[a]];
102 }
103 if (dep[a] > dep[b]) swap(a, b);
104 return a;
105 }
106 int Upto(int a, int b) {//返回u-r链上(除u)深度最小的点
107 int ans = inf;
108 while (top[a] != top[b]) {
109 if (dep[top[a]] < dep[top[b]]) swap(a, b);
110 if (top[a] != b) ans = tmin(ans, find(1, 1, n, id[top[a]], id[a]));
111 else ans = tmin(ans, find(1, 1, n, id[top[a]] + 1, id[a]));//不能包括b
112 a = fa[top[a]];
113 }
114 if (dep[a] > dep[b]) swap(a, b);
115 ans = tmin(ans, find(1, 1, n, id[a] + 1, id[b]));
116 return ans;
117 }
118 int check(int a) {//判断三种类型中的哪一种
119 if (a == rt) return 0;
120 int L = lca(a, rt);
121 if (L == a) return Upto(a, rt);
122 else return -1;
123 }
124 void Add_Chain(int a, int b, ll w) {//修改路径上的节点权值
125 while (top[a] != top[b]) {
126 if (dep[top[a]] < dep[top[b]]) swap(a, b);
127 update(1, 1, n, id[top[a]], id[a], w);
128 a = fa[top[a]];
129 }
130 if (dep[a] > dep[b]) swap(a, b);
131 update(1, 1, n, id[a], id[b], w);
132 }
133 ll Ask_Chain(int a, int b) {//查询路径节点权值和
134 ll ans = 0;
135 while (top[a] != top[b]) {
136 if(dep[top[a]] < dep[top[b]]) swap(a, b);
137 ans += query(1, 1, n, id[top[a]], id[a]);
138 a = fa[top[a]];
139 }
140 if (dep[a] > dep[b]) swap(a, b);
141 ans += query(1, 1, n, id[a], id[b]);
142 return ans;
143 }
144 void Add_Tree(int u, ll v) {//修改子树权值
145 int type = check(u);
146 if (!type) update(1, 1, n, 1, n, v);
147 else if (type > 0) {
148 update(1, 1, n, 1, n, v);
149 update(1, 1, n, id[type], id[type] + size[type] - 1, -v);
150 } else update(1, 1, n, id[u], id[u] + size[u] - 1, v);
151 }
152 ll Ask_Tree(int u) {
153 int type = check(u);
154 if (!type) return query(1, 1, n, 1, n);
155 else if (type > 0) {
156 //一定要写type>0,一开始我写的type(实际意思是type!=0)
157 //不然一直都是RE
158 ll ans = query(1, 1, n, id[type], id[type] + size[type] - 1);
159 return query(1, 1, n, 1, n) - ans;
160 } else return query(1, 1, n, id[u], id[u] + size[u] - 1);
161 }
162 }
163 using namespace SegmentTree;
164 int main() {
165 scanf("%d", &n);;
166 for (int i = 1; i <= n; i ++) scanf("%lld", &val[i]);
167 for (int i = 2; i <= n; i ++) {
168 scanf("%d", &a);
169 add(i, a), add(a, i);
170 }
171 dep[1] = 1;
172 dfs1(1, 0);
173 dfs2(1, 1);
174 build(1, 1, n);
175 scanf("%d", &m);
176 while (m --) {
177 scanf("%d", &opt);
178 if (opt == 1) {
179 scanf("%d", &a);
180 rt = a;
181 } else if (opt == 2) {
182 scanf("%d %d %d", &a, &b, &c);
183 Add_Chain(a, b, c);
184 } else if (opt == 3) {
185 scanf("%d %d", &a, &b);
186 Add_Tree(a, b);
187 } else if (opt == 4) {
188 scanf("%d %d", &a, &b);
189 printf("%lld\n", Ask_Chain(a, b));
190 } else {
191 scanf("%d", &a);
192 printf("%lld\n", Ask_Tree(a));
193 }
194 }
195 return 0;
196 }
代码量有点大，调试有点小困难。。。
标签：
留言评论