#include <bits/stdc++.h>
#define inf 1000000000
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int maxm = maxn << 1;
///图
vector<int> g[maxm];
///线段树
struct node{
int l, r;
ll sum, maxx;
int mid(){
return (l + r) >> 1;
}
}tree[maxn << 2];
///全局变量
int fa[maxn], dep[maxn], siz[maxn], son[maxn];///dfs1
int tim, dfn[maxn], top[maxn], w[maxn], val[maxn];///dfs2
void dfs1(int u, int f){
fa[u] = f;
dep[u] = dep[f] + 1;
siz[u] = 1;
int maxsize = -1;
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i];
if(v == f) continue;
dfs1(v, u);
siz[u] += siz[v];
if(siz[v] > maxsize){
maxsize = siz[v];
son[u] = v;
}
}
}
void dfs2(int u, int t){
dfn[u] = ++tim;
top[u] = t;
w[tim] = u;
if(!son[u]) return;
dfs2(son[u], t);
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i];
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
inline void PushUp(int root){
tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
tree[root].maxx = max(tree[root << 1].maxx, tree[root << 1 | 1].maxx);
}
void Build(int root, int l, int r){
tree[root].l = l;
tree[root].r = r;
if(l == r){
tree[root].sum = tree[root].maxx = val[w[l]];
return;
}
int mid = tree[root].mid();
Build(root << 1, l, mid);
Build(root << 1 | 1, mid + 1, r);
PushUp(root);
}
void UpDate(int root, int vis, int c){
if(tree[root].l == tree[root].r){
tree[root].sum = tree[root].maxx = c;
return;
}
int mid = tree[root].mid();
if(vis <= mid) UpDate(root << 1, vis, c);
else UpDate(root << 1 | 1, vis, c);
PushUp(root);
}
ll Query_sum(int root, int l, int r){
if(tree[root].l >= l && r >= tree[root].r) return tree[root].sum;
int mid = tree[root].mid();
if(r <= mid) return Query_sum(root << 1, l, r);
else if(l > mid) return Query_sum(root << 1 | 1, l, r);
else return Query_sum(root << 1, l, mid) + Query_sum(root << 1 | 1, mid + 1, r);
}
ll Query_max(int root, int l, int r){
if(tree[root].l >= l && r >= tree[root].r) return tree[root].maxx;
int mid = tree[root].mid();
if(r <= mid) return Query_max(root << 1, l, r);
else if(l > mid) return Query_max(root << 1 | 1, l, r);
else return max(Query_max(root << 1, l, mid), Query_max(root << 1 | 1, mid + 1, r));
}
inline void CHANGE(int x, int y){
UpDate(1, dfn[x], y);
}
inline ll QSUM(int x, int y){
ll res = 0;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]]) swap(x, y);
res += Query_sum(1, dfn[top[x]], dfn[x]);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
res += Query_sum(1, dfn[x], dfn[y]);
return res;
}
inline ll QMAX(int x, int y){
ll res = -((ll)1 << 60);
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]]) swap(x, y);
res = max(Query_max(1, dfn[top[x]], dfn[x]), res);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
res = max(Query_max(1, dfn[x], dfn[y]), res);
return res;
}
int main(){
int n, u, v, x, y, m;
char s[10];
scanf("%d", &n);
for(int i = 1; i < n; i++){
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1; i <= n; i++)
scanf("%d", &val[i]);
dfs1(1, 0);
dfs2(1, 1);
Build(1, 1, tim);
scanf("%d", &m);
getchar();
for(int i = 1; i <= m; i++){
scanf("%s", s);
if(s[0] == 'C'){
scanf("%d%d", &x, &y);
CHANGE(x, y);
}
else if(s[0] == 'Q' && s[1] == 'M'){
scanf("%d%d", &x, &y);
printf("%lld\n", QMAX(x, y));
}
else if(s[0] == 'Q' && s[1] == 'S'){
scanf("%d%d", &x, &y);
printf("%lld\n", QSUM(x, y));
}
}
return 0;
} 
查看11道真题和解析
