传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1036

保存模版。

执行qmax与qsum操作，往上爬的时候最开始的代码出了点小问题，往上爬的点应该是dep[top[u]]更深的点，而不是dep[u]更深的点。

#include
#include
#include
#include

const int maxn = 30005;

int n, q, t1, t2, root;
int head[maxn], to[maxn << 1], next[maxn << 1], lb, cnt;
int siz[maxn], dep[maxn], fa[maxn], id[maxn], heavy[maxn], v[maxn], top[maxn], a[maxn];
char opr[10];
struct Node {
int ql, qr, mx, sm;
} tree[maxn << 2];

inline void ist(int aa, int ss) {
to[lb] = ss;
next[lb] = head[aa];
head[aa] = lb;
++lb;
}
void dfs1(int r) {
siz[r] = 1;
dep[r] = dep[fa[r]] + 1;
int mx = 0, id = 0;
for (int j = head[r]; j != -1; j = next[j]) {
if (to[j] != fa[r]) {
fa[to[j]] = r;
dfs1(to[j]);
siz[r] += siz[to[j]];
if (siz[to[j]] > mx) {
mx = siz[id = to[j]];
}
}
}
heavy[r] = id;
}
void dfs2(int r, int tp) {
if (!r) {
return;
}
top[r] = tp;
id[r] = ++cnt;
a[cnt] = v[r];
dfs2(heavy[r], tp);
for (int j = head[r]; j != -1; j = next[j]) {
if (to[j] != fa[r] && to[j] != heavy[r]) {
dfs2(to[j], to[j]);
}
}
}
void make_tree(int p, int left, int right) {
tree[p].ql = left;
tree[p].qr = right;
if (left == right) {
tree[p].mx = tree[p].sm = a[left];
return;
}
int mid = (left + right) >> 1;
make_tree(p << 1, left, mid); make_tree(p << 1 | 1, mid + 1, right); tree[p].mx = std::max(tree[p << 1].mx, tree[p << 1 | 1].mx); tree[p].sm = tree[p << 1].sm + tree[p << 1 | 1].sm; } void upd(int p, int r, int value) { if (tree[p].ql == tree[p].qr) { tree[p].mx = tree[p].sm = value; return; } int mid = (tree[p].ql + tree[p].qr) >> 1;
if (r <= mid) { upd(p << 1, r, value); } else { upd(p << 1 | 1, r, value); } tree[p].mx = std::max(tree[p << 1].mx, tree[p << 1 | 1].mx); tree[p].sm = tree[p << 1].sm + tree[p << 1 | 1].sm; } int getmax(int p, int left, int right) { if (tree[p].ql == left && tree[p].qr == right) { return tree[p].mx; } int mid = (tree[p].ql + tree[p].qr) >> 1;
if (right <= mid) { return getmax(p << 1, left, right); } if (left > mid) {
return getmax(p << 1 | 1, left, right); } return std::max(getmax(p << 1, left, mid), getmax(p << 1 | 1, mid + 1, right)); } int getsum(int p, int left, int right) { if (tree[p].ql == left && tree[p].qr == right) { return tree[p].sm; } int mid = (tree[p].ql + tree[p].qr) >> 1;
if (right <= mid) { return getsum(p << 1, left, right); } if (left > mid) {
return getsum(p << 1 | 1, left, right);
}
return getsum(p << 1, left, mid) + getsum(p << 1 | 1, mid + 1, right);
}
int qmax(int u, int v) {
int rt = -2147483646;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) {
std::swap(u, v);
}
rt = std::max(rt, getmax(1, id[top[u]], id[u]));
u = fa[top[u]];
}
if (dep[u] < dep[v]) {
std::swap(u, v);
}
rt = std::max(rt, getmax(1, id[v], id[u]));
return rt;
}
int qsum(int u, int v) {
int rt = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) {
std::swap(u, v);
}
rt += getsum(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if (dep[u] < dep[v]) {
std::swap(u, v);
}
rt += getsum(1, id[v], id[u]);
return rt;
}

int main(void) {
//freopen("in.txt", "r", stdin);
unsigned seed;
memset(head, -1, sizeof head);
memset(next, -1, sizeof next);
scanf("%d", &n);
seed += n;
for (int i = 1; i < n; ++i) {
scanf("%d%d", &t1, &t2);
ist(t1, t2);
ist(t2, t1);
seed += t1;
}
for (int i = 1; i <= n; ++i) {
scanf("%d", v + i);
}

srand(seed);  
root = rand() % n + 1;  
dfs1(root);  
dfs2(root, root);  
make\_tree(1, 1, n);

scanf("%d", &q);  
while (q--) {  
    scanf("%s%d%d", opr, &t1, &t2);  
    if (opr\[1\] == 'M') {  
        printf("%d\\n", qmax(t1, t2));  
    }  
    else if (opr\[1\] == 'S') {  
        printf("%d\\n", qsum(t1, t2));  
    }  
    else {  
        upd(1, id\[t1\], t2);  
    }  
}  
return 0;  

}