/*
HYSBZ1036
树上有1-n个结点，每个节点都有一个权值w
操作 CHANGE u t:把结点u的权值改为t
QMAX u v:询问从点u到v的路径上的节点的最大权值
QSUM u v:询问从点u到v的路径上的结点的权值和
从点u到点v路径上的结点包括u，v本身
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define MAXN 30010
using namespace std;
struct Edge{
int to, next;
}edge[MAXN*
2];
int head[MAXN], tot;
int top[MAXN];
//重链顶端
int fa[MAXN];
//父亲
int deep[MAXN];
//深度，root=1
int num[MAXN];
//子节点数
int p[MAXN];
//v在线段树中的位置
int fp[MAXN];
int son[MAXN];
//重儿子
int pos;
void init(){
tot =
0;
memset(head, -
1,
sizeof(head));
pos =
0;
memset(son, -
1,
sizeof(son));
}
void addedge(
int u,
int v){
edge[tot].to =
v;
edge[tot].next =
head[u];
head[u] = tot++
;
}
//第一次dfs求fa,deep,son,num
void dfs1(
int u,
int pre,
int d){
deep[u] =
d;
fa[u] =
pre;
num[u] =
1;
for(
int i = head[u]; i != -
1; i =
edge[i].next){
int v =
edge[i].to;
if (v !=
pre){
dfs1(v, u, d+
1);
num[u]+=
num[v];
if (son[u]==-
1||num[v]>
num[son[u]])
son[u] =
v;
}
}
}
//第二次dfs求top，p,用pos记数
void getpos(
int u,
int sp){
//sp表示重链顶端
top[u] =
sp;
p[u] = pos++
;
fp[p[u]] =
u;
if (son[u]==-
1)
return;
getpos(son[u], sp);//先把重儿子查到底
for(
int i = head[u]; i != -
1; i =
edge[i].next){
int v = edge[i].to;
//轻儿子
if (v != son[u] && v !=
fa[u])
getpos(v, v);
}
}
//线段树部分
struct Node{
int l, r;
int sum;
int Max;
}segTree[MAXN*
3];
inline void push_up(
int i){
segTree[i].sum = segTree[i<<
1].sum + segTree[i<<
1|
1].sum;
segTree[i].Max = max(segTree[i<<
1].Max, segTree[i<<
1|
1].Max);
}
int s[MAXN];
void build(
int i,
int l,
int r){
segTree[i].l =
l;
segTree[i].r =
r;
if (l==
r){
segTree[i].sum = segTree[i].Max =
s[fp[l]];
return;
}
int mid = l+r >>
1;
build(i<<
1, l, mid);
build(i<<
1|
1, mid+
1, r);
push_up(i);
}
//更新线段树的第k个值为val
void update(
int i,
int k,
int val){
if(segTree[i].l == k && segTree[i].r ==
k){
segTree[i].Max = segTree[i].sum =
val;
return;
}
int mid = segTree[i].l + segTree[i].r >>
1;
if (k <=
mid)
update(i<<
1, k, val);
else
update(i<<
1|
1, k, val);
push_up(i);//单点更新后要重新计算Max和Sum
}
//查询[l,r]区间的最大值
int queryMax(
int i,
int l,
int r){
if(segTree[i].l == l && segTree[i].r ==
r)
return segTree[i].Max;
int mid = segTree[i].l+segTree[i].r >>
1;
if (r <=
mid)
return queryMax(i<<
1, l, r);
else if (l >
mid)
return queryMax(i<<
1|
1, l, r);
else
return max(queryMax(i<<
1, l, mid), queryMax(i<<
1|
1, mid+
1, r));
}
//查询[l,r]区间的和
int querySum(
int i,
int l,
int r){
if(segTree[i].l==l && segTree[i].r ==
r)
return segTree[i].sum;
int mid = segTree[i].l+segTree[i].r>>
1;
if(r <=
mid)
return querySum(i<<
1,l,r);
else if(l >
mid)
return querySum((i<<
1)|
1,l,r);
else
return querySum(i<<
1, l, mid)+querySum(i<<
1|
1, mid+
1, r);
}
//查询u->v路径上结点的最大权值
int findMax(
int u,
int v){
int f1 = top[u], f2 =
top[v];
int tmp = -
1000000000;
while(f1!=f2){
//不在同一条重链上时
if(deep[f1]<
deep[f2]){
swap(u, v);
swap(f1, f2);
}
tmp = max(tmp, queryMax(
1, p[f1], p[u]));
//把这一条链上的求出来
u =
fa[f1];
f1 =
top[u];
}
if (deep[u]>
deep[v])
swap(u,v);
return
max(tmp, queryMax(1, p[u], p[v]));
}
//查询u->v路径上结点的权值
int findSum(
int u,
int v){
int f1 =
top[u];
int f2 =
top[v];
int tmp =
0;
while(f1 !=
f2){
if (deep[f1] <
deep[f2]){
swap(f1, f2);
swap(u, v);
}
tmp += querySum(
1, p[f1], p[u]);
u =
fa[f1];
f1 =
top[u];
}
if(deep[u]>
deep[v])
swap(u, v);
return tmp + querySum(
1, p[u], p[v]);
}
int main(){
int n;
int q;
char op[
20];
int u, v;
while(scanf(
"%d", &n)==
1){
init();
for(
int i =
1; i < n; i++
){
scanf("%d%d", &u, &
v);
addedge(u, v);
addedge(v, u);
}
for(
int i =
1; i <= n; i++
)
scanf("%d", &
s[i]);
dfs1(1,
0,
0);
getpos(1,
1);
build(1,
0, pos-
1);
scanf("%d", &
q);
while(q--
){
scanf("%s%d%d", op, &u, &
v);
if (op[
0]==
'C')
update(1, p[u], v);
//单点修改
else if (strcmp(op,
"QMAX")==
0)
printf("%d\n", findMax(u, v));
//查询u->v路径上点权的最大值
else
printf("%d\n", findSum(u, v));
//查询路径上点权的和
}
}
return 0;
}
转载于:https://www.cnblogs.com/zsben991126/p/10045252.html
