1、题目大意：给你一棵树，有三种操作
1>qmax，询问u到v中间点权的最大值
2>qsum，询问u到v中间点权和
3>change，把u这个节点的权值改为v
2、分析：树链剖分的裸题，搞了一个礼拜。。。
需要维护的东西
1>height[x] x的深度
2>Top[x] x所在树链的最顶端
3>num[x] x在线段树的标号
4>father[x] x的父亲
5>size[x] 以x为根的字数的节点数
6>value[x] x的权值
7>segment_tree
哪个儿子的size最大，那么连着这个儿子的边就是重边
然后比如求点权最大值，然后就让Top值最大的那个点往上跳到father[Top[这个点]]，更新ret，直到u和v是同一个链上的
线段树就搞一搞，求和也是类似的，修改就是线段树单点的修改
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct segment_tree{
int q[1001000];
int sum[1001000];
int x, y;
void init(){
for(int i = 1; i <= 1000000; i ++) q[i] = -2147483647;
return;
}
void add(int l, int r, int o){
if(l == r && x == l){
sum[o] = q[o] = y;
return;
}
int mid = (l + r) / 2;
if(x <= mid) add(l, mid, 2 * o);
if(x > mid) add(mid + 1, r, 2 * o + 1);
q[o] = max(q[2 * o], q[2 * o + 1]);
sum[o] = sum[2 * o] + sum[2 * o + 1];
return;
}
int query_max(int l, int r, int o){
if(x <= l && r <= y){
return q[o];
}
int mid = (l + r) / 2;
int ret = -2147483647;
if(x <= mid) ret = max(ret, query_max(l, mid, 2 * o));
if(y > mid) ret = max(ret, query_max(mid + 1, r, 2 * o + 1));
return ret;
}
int query_sum(int l, int r, int o){
if(x <= l && r <= y){
return sum[o];
}
int mid = (l + r) / 2;
int ret = 0;
if(x <= mid) ret += query_sum(l, mid, 2 * o);
if(y > mid) ret += query_sum(mid + 1, r, 2 * o + 1);
return ret;
}
} qzh;
struct node{
int from, to, next;
};
struct tree_chain_partition{
int Top[1000100];
int Size[1000100];
int height[1000100];
int father[1000100];
int num[1000100];
int value[1000100];
node G[1000100];
int head[1000100];
int ff;
int de;
int n;
void init(){
memset(head, -1, sizeof(head));
ff = -1;
return;
}
void insert(int u, int v){
ff ++;
G[ff] = (node){u, v, head[u]};
head[u] = ff;
return;
}
void dfs1(int x, int fa, int k){
father[x] = fa;
height[x] = k;
Size[x] = 1;
for(int i = head[x]; i != -1; i = G[i].next){
node e = G[i];
if(e.to != fa){
dfs1(e.to, x, k + 1);
Size[x] += Size[e.to];
}
}
return;
}
void dfs2(int x, int fa){
int o = 0, pos;
for(int i = head[x]; i != -1; i = G[i].next){
node e = G[i];
if(Size[e.to] > o && e.to != fa){
pos = i;
o = Size[e.to];
}
}
if(o != 0){
qzh.x = ++ de;
qzh.y = value[G[pos].to];
qzh.add(1, n, 1);
num[G[pos].to] = de;
Top[G[pos].to] = Top[x];
dfs2(G[pos].to, x);
}
for(int i = head[x]; i != -1; i = G[i].next){
node e = G[i];
if(e.to != fa && i != pos){
qzh.x = ++ de;
qzh.y = value[e.to];
qzh.add(1, n, 1);
num[e.to] = de;
Top[e.to] = e.to;
dfs2(e.to, x);
}
}
return;
}
void solve(){
qzh.init();
dfs1(1, 0, 1);
qzh.x = ++ de;
qzh.y = value[1];
qzh.add(1, n, 1);
num[1] = de;
Top[1] = 1;
dfs2(1, 0);
return;
}
void change(int s, int t){
qzh.x = num[s];
qzh.y = t;
qzh.add(1, n, 1);
return;
}
int qmax(int s, int t){
int ret = -2147483647;
while(Top[s] != Top[t]){
if(height[Top[s]] > height[Top[t]]) swap(s, t);
qzh.x = num[Top[t]];
qzh.y = num[t];
ret = max(ret, qzh.query_max(1, n, 1));
t = father[Top[t]];
}
if(height[s] > height[t]) swap(s, t);
qzh.x = num[s];
qzh.y = num[t];
ret = max(ret, qzh.query_max(1, n, 1));
return ret;
}
int qsum(int s, int t){
int ret = 0;
while(Top[s] != Top[t]){
if(height[Top[s]] > height[Top[t]]) swap(s, t);
qzh.x = num[Top[t]];
qzh.y = num[t];
ret += qzh.query_sum(1, n, 1);
t = father[Top[t]];
}
if(height[s] > height[t]) swap(s, t);
qzh.x = num[s];
qzh.y = num[t];
ret += qzh.query_sum(1, n, 1);
return ret;
}
} wt;
int main(){
wt.init();
scanf("%d", &wt.n);
for(int i = 1; i < wt.n; i ++){
int u, v;
scanf("%d%d", &u, &v);
wt.insert(u, v);
wt.insert(v, u);
}
for(int i = 1; i <= wt.n; i ++) scanf("%d", &wt.value[i]);
int q;
scanf("%d", &q);
wt.solve();
while(q --){
char str[10];
int u, v;
scanf("%s%d%d", str, &u, &v);
if(str[1] == 'H') wt.change(u, v);
else if(str[1] == 'M') printf("%d\n", wt.qmax(u, v));
else printf("%d\n", wt.qsum(u, v));
}
return 0;
}