比较基础的一道树链剖分的题 大概还是得说说思路
树链剖分是将树剖成很多条链，比较常见的剖法是按儿子的size来剖分，剖分完后对于这课树的询问用线段树维护——比如求路径和的话——随着他们各自的链向上走，直至他们在同一条链上为止。比较像lca的方法，只不过这里是按链为单位，而且隔壁的SymenYang说可以用树链剖分做lca。。吓哭
然后说说惨痛的调题经历：边表一定要开够啊！ 不是n-1 而是2*（n-1）啊！ 然后写变量时原始值和映射值要搞清楚啊！ 不要搞错了！ 还有就是下次求最小值一定看清下界是多少！ 树的统计是-30000 ~ 30000 ,我果断naive 的写了一个初值为0！！！ wa 0 就是这么痛苦！ 还是too Young too Simple !
code :
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ; struct edge{
int t; edge* next;
}e[maxn*], *head[maxn];int ne = ; void addedge(int f, int t){
e[ne].t = t; e[ne].next = head[f]; head[f] = e + ne ++;
} int n;
int size[maxn],fa[maxn],dep[maxn],w[maxn],un[maxn],map[maxn]; struct node{
int smax, sum;
node *l, *r;
}tr[maxn * ], *root; int trne = ; node* build(int l, int r){
node* x = tr + trne ++;
if(l != r) {
int mid = (l + r) >> ;
x-> l = build(l, mid);
x-> r = build(mid + , r);
}
return x;
} void update(node* x){
if(x-> l) {
x-> sum = x-> l-> sum + x-> r->sum;
x-> smax = max(x-> l-> smax, x-> r-> smax);
}
} void insert(node* x, int l, int r, int pos, int v) {
if(l == r) { x-> sum = v, x-> smax = v;}
else{
int mid = (l + r) >> ;
if(pos <= mid) insert(x-> l, l, mid, pos, v);
else insert(x-> r, mid + , r, pos, v);
update(x);
}
} int ask(node* x, int l, int r, int ls, int rs, int flag) {
if(l == ls && r == rs) {
if(flag == ) return x-> smax;
else return x-> sum;
}
else {
int mid = (l + r) >> ;
if(rs <= mid) return ask(x-> l, l, mid, ls, rs, flag);
else if(ls >= mid + ) return ask(x-> r, mid + , r, ls, rs, flag);
else {
if(flag == )
return max(ask(x->l, l, mid, ls, mid, flag), ask(x-> r, mid + , r, mid + , rs, flag));
else
return ask(x-> l, l, mid, ls, mid, flag) + ask(x-> r, mid + , r, mid + , rs, flag);
}
}
} int cnt = ; void size_cal(int x, int pre) {
if(pre == -) dep[x] = , fa[x] = x;
else dep[x] = dep[pre] + , fa[x] = pre; size[x] = ;
for(edge* p = head[x]; p; p = p-> next)
if(dep[p-> t] == -)size_cal(p-> t, x), size[x] += size[p-> t];
} void divide(int x, int pre){
if(pre == -) un[x] = x;
else un[x] = un[pre];
map[x] = ++ cnt; insert(root, , n, map[x], w[x]);
int tmax = -, ts = -;
for(edge* p = head[x]; p; p = p-> next) {
if(dep[p-> t] > dep[x] && size[p-> t] > tmax) tmax = size[p-> t], ts = p-> t;
}
if(ts != -) {
divide(ts, x);
for(edge* p = head[x]; p; p = p-> next) {
if(dep[p-> t] > dep[x] && p-> t != ts) divide(p-> t, -);
}
}
} void read() {
memset(dep,-,sizeof(dep));
scanf("%d", &n);
root = build(, n);
for(int i = ; i <= n - ; i++) {
int f, t;
scanf("%d%d", &f, &t);
addedge(f, t), addedge(t, f);
}
for(int i = ; i <= n; ++ i) {
scanf("%d", &w[i]);
}
size_cal(, -);divide(, -);
} int sovmax(int a, int b) {
int ans = -; int ls, rs;
while(un[a] != un[b]) {
if(dep[un[a]] > dep[un[b]]) {
ls = map[a]; rs = map[un[a]];
if(ls > rs) swap(ls, rs);
ans = max(ans, ask(root, , n, ls, rs, ));
a = fa[un[a]];
}
else {
ls = map[b]; rs = map[un[b]];
if(ls > rs) swap(ls, rs);
ans = max(ans, ask(root, , n, ls, rs, ));
b = fa[un[b]];
}
}
ls = map[a], rs = map[b];
if(ls > rs) swap(ls,rs);
ans = max(ans, ask(root, , n, ls, rs, ));
return ans;
} int sovsum(int a,int b) {
int ans = ; int ls, rs;
while(un[a] != un[b]) {
if(dep[un[a]] > dep[un[b]]) {
ls = map[a], rs = map[un[a]];
if(ls > rs) swap(ls, rs);
ans += ask(root, , n, ls, rs, );
a = fa[un[a]];
}
else {
ls = map[b]; rs = map[un[b]];
if(ls > rs) swap(ls, rs);
ans += ask(root, , n, ls, rs, );
b = fa[un[b]];
}
}
ls = map[a], rs = map[b];
if(ls > rs) swap(ls, rs);
ans += ask(root, , n, ls, rs, );
return ans;
} void sov() {
int m;
scanf("%d", &m);
while(m --) {
char s[]; int ls, rs;
scanf("%s %d%d", s + , &ls, &rs);
if(s[] == 'M') printf("%d\n", sovmax(ls, rs));
if(s[] == 'S') printf("%d\n", sovsum(ls, rs));
if(s[] == 'H') insert(root, , n, map[ls], rs);
}
} int main(){
read();sov();
return ;
}