树链剖分 HYSBZ1036 [ZJOI2008]树的统计 _生活百科

将树通过树链剖分转化成线性序列，用线段树维护最值，和值即可。
1 #include <bits/stdc++.h>2 using namespace std;3 const int N = 3e4 + 10;4 int n, m, head[N], to[N << 1], nxt[N << 1], tot;5 int total, fa[N], dep[N], size[N], son[N], top[N];6 int w[N], id[N], rev[N];7 int Max, Sum;8 struct node{9int mx, sum; 10 }t[N << 2]; 11 void add(int x, int y) { 12nxt[++ tot] = head[x]; head[x] = tot; to[tot] = y; 13 } 14 void dfs1(int u, int f) { //求dep,fa,size,son 15size[u] = 1; 16for (int i = head[u]; i; i = nxt[i]) { 17int v = to[i]; 18if (v == f) continue; 19dep[v] = dep[u] + 1; 20fa[v] = u; 21dfs1(v, u); 22size[u] += size[v]; 23if (size[v] > size[son[u]]) son[u] = v; 24} 25 } 26 void dfs2(int u, int t) { //求top,id,rev 27top[u] = t; 28id[u] = ++ total; // u对应的dfs序下标 29rev[total] = u;// dfs序下标对应的u 30if (!son[u]) return ; 31dfs2(son[u], t);//先沿重儿子dfs 32for (int i = head[u]; i; i = nxt[i]) { 33int v = to[i]; 34if (v != fa[u] && v != son[u]) dfs2(v, v); 35} 36 } 37 namespace SegmentTree { 38#define mid ((l + r) >> 1) 39#define lson k << 1, l, mid 40#define rson k << 1 | 1, mid + 1, r 41void pushup(int k) { 42t[k].mx = max(t[k << 1].mx, t[k << 1 | 1].mx); 43t[k].sum = t[k << 1].sum + t[k << 1 | 1].sum; 44} 45void build(int k, int l, int r) { 46if (l == r) { 47t[k].mx = t[k].sum = w[rev[l]]; 48return ; 49} 50build(lson), build(rson); 51pushup(k); 52} 53void update(int k, int l, int r, int pos, int v) { 54if (l == r) { 55t[k].mx = t[k].sum = v; 56return ; 57} 58if (pos <= mid) update(lson, pos, v); 59else update(rson, pos, v); 60pushup(k); 61} 62void query(int k, int l, int r, int L, int R) { 63if (L <= l && R >= r) { 64Max = max(Max, t[k].mx); 65Sum += t[k].sum; 66return ; 67} 68if (L <= mid) query(lson, L, R); 69if (R > mid) query(rson, L, R); 70} 71void ask(int u, int v) { 72while (top[u] != top[v]) { 73if(dep[top[u]] < dep[top[v]]) swap(u, v); 74query(1, 1, total, id[top[u]], id[u]); 75u = fa[top[u]]; 76} 77if (dep[u] > dep[v]) swap(u, v); 78query(1, 1, total, id[u], id[v]); 79} 80 } 81 using namespace SegmentTree; 82 int main() { 83int x, y; char str[10]; 84scanf("%d", &n); 85for (int i = 1; i < n; i ++) { 86scanf("%d %d", &x, &y); 87add(x, y), add(y, x); 88} 89for (int i = 1; i <= n; i ++) scanf("%d", &w[i]); 90dep[1] = 1; 91dfs1(1, 0); 92dfs2(1, 1); 93build(1, 1, total); 94scanf("%d", &m); 95for (int i = 1; i <= m; i ++) { 96scanf("%s", str); 97scanf("%d %d", &x, &y); 98if(str[0] == 'C') update(1, 1, total, id[x], y); 99else {100Sum = 0;101Max = -0x3f3f3f3f;102ask(x, y);103if (str[1] == 'M') printf("%d\n", Max);104else printf("%d\n", Sum);105}106}107return 0;108 }【树链剖分 HYSBZ1036 [ZJOI2008]树的统计】

树链剖分 HYSBZ1036 [ZJOI2008]树的统计

推荐阅读

第一灭火力量在几分钟内形成第一灭火力量在几分钟内形成救援力量

哪些星座的胖子最多

鸭肉炖白萝卜的做法

一不小心被女生骂成了狗,表白,准备好了吗

若是按最低档社保缴纳15年，退休后每个月能拿多少钱？

长喝苹果加西红柿汁有什么好处

通话录音在哪里找到安卓手机通话录音在哪里找到

4两8男命详解

天秤座干不了的职业

适合情侣晚上在家看的电影这个杀手不太冷适合情侣晚上在家看的电影

最适合双子座看的动画片

安全证书过期怎么办安全证书过期

隔沙肉是什么部位

皮面羽绒服可以用洗衣机洗吗皮面羽绒服怎么清洗呢

属猪和属猴相合吗

父母想要离婚怎么办办离婚怎么办

港澳签注港澳签注有效期

初中地理教学工作年度总结学校初中地理教学工作反思5篇

疯狂动物园攻略合集-新手指南常见问题解答[多图]

狗脊的功效与作用