树链剖分
捡起来好久没写的树剖。。。竟然没有写挂。。一次过了。。。
就是用线段树来维护一颗树上的dfs序
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define full(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long ll;
inline int lowbit(int x){ return x & (-x); }
inline int read(){
int X = 0, w = 0; char ch = 0;
while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
return w ? -X : X;
}
inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }
inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
template<typename T>
inline T max(T x, T y, T z){ return max(max(x, y), z); }
template<typename T>
inline T min(T x, T y, T z){ return min(min(x, y), z); }
template<typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){
A ans = 1;
for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
return ans;
}
const int N = 30005;
int n, cnt, dfn, head[N], depth[N], size[N], son[N], p[N], top[N], id[N], w[N], val[N];
int tree[N<<2], m[N<<2];
struct Edge { int v, next; } edge[N<<1];
void addEdge(int a, int b){
edge[cnt].v = b, edge[cnt].next = head[a], head[a] = cnt ++;
}
void dfs1(int s, int fa){
depth[s] = depth[fa] + 1;
p[s] = fa;
size[s] = 1;
int child = -1;
for(int i = head[s]; i != -1; i = edge[i].next){
int u = edge[i].v;
if(u == fa) continue;
dfs1(u, s);
size[s] += size[u];
if(size[u] > child) child = size[u], son[s] = u;
}
}
void dfs2(int s, int tp){
id[s] = ++dfn;
w[id[s]] = val[s];
top[s] = tp;
if(son[s] != -1) dfs2(son[s], tp);
for(int i = head[s]; i != -1; i = edge[i].next){
int u = edge[i].v;
if(u == p[s] || u == son[s]) continue;
dfs2(u, u);
}
}
void push_up(int rt){
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
m[rt] = max(m[rt << 1], m[rt << 1 | 1]);
}
void buildTree(int rt, int l, int r){
if(l == r){
tree[rt] = m[rt] = w[l];
return;
}
int mid = (l + r) >> 1;
buildTree(rt << 1, l, mid);
buildTree(rt << 1 | 1, mid + 1, r);
push_up(rt);
}
void modify(int rt, int l, int r, int k, int t){
if(l == r){
tree[rt] = m[rt] = t;
return;
}
int mid = (l + r) >> 1;
if(k <= mid) modify(rt << 1, l, mid, k, t);
else modify(rt << 1 | 1, mid + 1, r, k, t);
push_up(rt);
}
int queryMax(int rt, int l, int r, int queryL, int queryR){
if(l == queryL && r == queryR){
return m[rt];
}
int mid = (l + r) >> 1;
if(queryL > mid) return queryMax(rt << 1 | 1, mid + 1, r, queryL, queryR);
else if(queryR <= mid) return queryMax(rt << 1, l, mid, queryL, queryR);
else return max(queryMax(rt << 1, l, mid, queryL, mid),
queryMax(rt << 1 | 1, mid + 1, r, mid + 1, queryR));
}
int querySum(int rt, int l, int r, int queryL, int queryR){
if(l == queryL && r == queryR){
return tree[rt];
}
int mid = (l + r) >> 1;
if(queryL > mid) return querySum(rt << 1 | 1, mid + 1, r, queryL, queryR);
else if(queryR <= mid) return querySum(rt << 1, l, mid, queryL, queryR);
else return querySum(rt << 1, l, mid, queryL, mid) +
querySum(rt << 1 | 1, mid + 1, r, mid + 1, queryR);
}
int treeMax(int x, int y){
int ret = -INF;
while(top[x] != top[y]){
if(depth[top[x]] < depth[top[y]]) swap(x, y);
ret = max(ret, queryMax(1, 1, n, id[top[x]], id[x]));
x = p[top[x]];
}
if(depth[x] > depth[y]) swap(x, y);
return max(ret, queryMax(1, 1, n, id[x], id[y]));
}
int treeSum(int x, int y){
int ret = 0;
while(top[x] != top[y]){
if(depth[top[x]] < depth[top[y]]) swap(x, y);
ret += querySum(1, 1, n, id[top[x]], id[x]);
x = p[top[x]];
}
if(depth[x] > depth[y]) swap(x, y);
ret += querySum(1, 1, n, id[x], id[y]);
return ret;
}
int main(){
full(head, -1);
full(son, -1);
n = read();
for(int i = 0; i < n - 1; i ++){
int u = read(), v = read();
addEdge(u, v), addEdge(v, u);
}
for(int i = 1; i <= n; i ++) val[i] = read();
dfs1(1, 0), dfs2(1, 1);
buildTree(1, 1, n);
int q = read();
while(q --){
char opt[10]; scanf("%s", opt);
if(opt[1] == 'H'){
int x = read(), y = read();
modify(1, 1, n, id[x], y);
}
else if(opt[1] == 'M'){
int x = read(), y = read();
printf("%d
", treeMax(x, y));
}
else if(opt[1] == 'S'){
int x = read(), y = read();
printf("%d
", treeSum(x, y));
}
}
return 0;
}