Description
一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成 一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v:询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身
Input
输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有 一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
Output
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
Sample Input
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
Sample Output
4
1
2
2
10
6
5
6
5
16
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long LL; const int SZ = 400010; struct SGT { int l, r; LL sum, maxx; }sgt[SZ]; struct Tree { int f, t; }tree[SZ]; int size[SZ], first[SZ], nxt[SZ], fa[SZ], deep[SZ], son[SZ], num[SZ], tot; void Build(int f, int t) { tree[++tot] = (Tree){f, t}; nxt[tot] = first[f]; first[f] = tot; } void DFS_1(int u, int f) { fa[u] = f; deep[u] = deep[f] + 1; size[u] = 1; for(int i = first[u]; i; i = nxt[i]) { int v = tree[i].t; if(v == f) continue; DFS_1(v, u); size[u] += size[v]; if(!son[u] || size[v] > size[son[u]]) son[u] = v; } } int top[SZ], inseg[SZ], intree[SZ], topa; void DFS_2(int u, int topu) { top[u] = topu; inseg[u] = ++ topa; intree[topa] = u; if(!son[u]) return ; DFS_2(son[u], topu); for(int i = first[u]; i; i = nxt[i]) { int v = tree[i].t; if(v == son[u] || v == fa[u]) continue; DFS_2(v, v); } } void update(int now) { sgt[now].sum = sgt[now << 1].sum + sgt[now << 1 | 1].sum; sgt[now].maxx = max(sgt[now << 1].maxx, sgt[now << 1 | 1].maxx); } void Build_Tree(int now, int l, int r) { sgt[now].l = l; sgt[now].r = r; if(l == r) { sgt[now].sum = sgt[now].maxx = num[intree[l]]; return ; } int mid = (l + r) >> 1; Build_Tree(now << 1, l, mid); Build_Tree(now << 1 | 1, mid + 1, r); update(now); } void Change(int now, int point, int value) { if(sgt[now].l == sgt[now].r) { sgt[now].sum = value; sgt[now].maxx = value; return ; } int mid = (sgt[now].l + sgt[now].r) >> 1; if(point <= mid) Change(now << 1, point, value); if(point > mid) Change(now << 1 | 1, point, value); update(now); } LL Ask_Max(int now, int l, int r) { if(l <= sgt[now].l && sgt[now].r <= r) return sgt[now].maxx; int mid = (sgt[now].l + sgt[now].r) >> 1; LL maxn = -SZ; if(l <= mid) maxn = max(maxn, Ask_Max(now << 1, l, r)); if(r > mid) maxn = max(maxn, Ask_Max(now << 1 | 1, l, r)); return maxn; } LL Ask_Sum(int now, int l, int r) { if(l <= sgt[now].l && sgt[now].r <= r) return sgt[now].sum; int mid = (sgt[now].l + sgt[now].r) >> 1; LL sum = 0; if(l <= mid) sum += Ask_Sum(now << 1, l, r); if(r > mid) sum += Ask_Sum(now << 1 | 1, l, r); return sum; } LL Max(int l, int r) { int fal = top[l], far = top[r]; LL maxn = -SZ; while(fal != far) { if(deep[fal] < deep[far]) { swap(l, r); swap(fal, far); } maxn = max(maxn, Ask_Max(1, inseg[fal], inseg[l])); l = fa[fal]; fal = top[l]; } if(deep[l] > deep[r]) swap(l, r); maxn = max(maxn, Ask_Max(1, inseg[l], inseg[r])); return maxn; } LL Sum(int l, int r) { int fal = top[l], far = top[r]; LL ans = 0; while(fal != far) { if(deep[fal] < deep[far]) swap(l, r), swap(fal, far); ans += Ask_Sum(1, inseg[fal], inseg[l]); l = fa[fal]; fal = top[l]; } if(deep[l] > deep[r]) swap(l, r); ans += Ask_Sum(1, inseg[l], inseg[r]); return ans; } int main() { int n; scanf("%d", &n); int f, t; for(int i = 1; i < n; i++) { scanf("%d%d", &f, &t); Build(f, t); Build(t, f); } for(int i = 1; i <= n; i++) scanf("%d", &num[i]); DFS_1(1, 0); DFS_2(1, 1); Build_Tree(1, 1, n); int q; char op[10]; int a, b; scanf("%d", &q); for(int i = 1; i <= q; i++) { scanf("%s", op); scanf("%d%d", &a, &b); if(op[0] == 'Q' && op[1] == 'M') printf("%lld\n", Max(a, b)); else if (op[0] == 'Q' && op[1] == 'S') printf("%lld\n", Sum(a, b)); else Change(1, inseg[a], b), num[a] = b; } return 0; }转载于:https://www.cnblogs.com/Loi-Vampire/p/6017051.html
