显示代码纯文本
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
const int INF=1e8;
const int MAXN=30000+10;
vector<int> G[MAXN];
struct seg_tree{
struct node{
int num,mx_num,sum;
int left,right;
int left_son,right_son;
node(int left=0,int right=0):
left(left),right(right){
num=mx_num=sum=-INF;
left_son=right_son=0;
}
}nodes[MAXN*3];
int node_cnt;
void init(){
node_cnt=0;
}
seg_tree(){
init();
}
void update(int no){
node & now=nodes[no];
now.mx_num=-INF;
if(now.left_son!=0 && now.right_son!=0){
node & left_node=nodes[now.left_son];
node & right_node=nodes[now.right_son];
now.mx_num=max(left_node.mx_num,right_node.mx_num);
now.sum=left_node.sum+right_node.sum;
}else{
now.mx_num=now.num;
now.sum=now.num;
}
}
void build_tree(int no,int left,int right,int info[]){
node & now=nodes[no];
now=node(left,right);
if(left==right){
now.num=info[left];
}else{
int mid=(left+right)/2;
now.left_son=node_cnt;
build_tree(node_cnt++,left,mid,info);
now.right_son=node_cnt;
build_tree(node_cnt++,mid+1,right,info);
}
update(no);
}
int get_max_num(int no,int left,int right){
node & now=nodes[no];
if(now.left>right || now.right<left) return -INF;
else if(now.left>=left && now.right<=right){
return now.mx_num;
}else{
int ret=-INF;
ret=max(ret,get_max_num(now.left_son,left,right));
ret=max(ret,get_max_num(now.right_son,left,right));
return ret;
}
}
int get_sum(int no,int left,int right){
node & now=nodes[no];
if(now.left>right || now.right<left)return 0;
else if(now.left>=left && now.right<=right){
return now.sum;
}else {
int ret=0;
ret+=get_sum(now.left_son,left,right);
ret+=get_sum(now.right_son,left,right);
return ret;
}
}
void change_num(int no,int mu,int num){
node & now=nodes[no];
if(now.left==now.right){
now.num=num;
}else{
int mid=(now.left+now.right)/2;
if(mu<=mid)change_num(now.left_son,mu,num);
else change_num(now.right_son,mu,num);
}
update(no);
}
};
struct light_heavy_dec{
int fa[MAXN],son[MAXN],deep[MAXN],size[MAXN],top[MAXN],map_to_tree[MAXN];
int dfs_clock;
seg_tree st;
void init(){
st.init();
dfs_clock=1;
memset(fa,0,sizeof(fa));
memset(son,0,sizeof(son));
memset(deep,0,sizeof(deep));
memset(size,0,sizeof(size));
memset(top,0,sizeof(top));
memset(map_to_tree,0,sizeof(map_to_tree));
}
light_heavy_dec(){
init();
}
void dfs1(int u,int fa_,int deep_){
fa[u]=fa_;
deep[u]=deep_;
size[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v!=fa_){
dfs1(v,u,deep_+1);
size[u]+=size[v];
}
}
}
void dfs2(int u,int fa_top){
top[u]=fa_top;
map_to_tree[u]=dfs_clock++;
int mx_size=0;
int mx_heavy_son=0;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa[u])continue;
if(size[v]>mx_size)mx_size=size[v],mx_heavy_son=v;
}
if(mx_size!=0){
dfs2(mx_heavy_son,fa_top);
son[u]=mx_heavy_son;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa[u] || v==mx_heavy_son)continue;
dfs2(v,v);
}
}
}
int get_sum(int u,int v){
int f1=top[u];int f2=top[v];
int ret=0;
while(f1!=f2){
if(deep[f1]<deep[f2])swap(f1,f2),swap(u,v);
ret+=st.get_sum(0,map_to_tree[f1],map_to_tree[u]);
u=fa[f1];
f1=top[u];
}
if(map_to_tree[u]>map_to_tree[v])swap(u,v);
ret+=st.get_sum(0,map_to_tree[u],map_to_tree[v]);
return ret;
}
int get_max(int u,int v){
int f1=top[u];int f2=top[v];
int ret=-INF;
while(f1!=f2){
if(deep[f1]<deep[f2])swap(f1,f2),swap(u,v);
ret=max(ret,st.get_max_num(0,map_to_tree[f1],map_to_tree[u]));
u=fa[f1];
f1=top[u];
}
if(map_to_tree[u]>map_to_tree[v])swap(u,v);
ret=max(ret,st.get_max_num(0,map_to_tree[u],map_to_tree[v]));
return ret;
}
void change_num(int u,int num){
st.change_num(0,map_to_tree[u],num);
}
void build(int info[]){
st.build_tree(st.node_cnt++,1,size[1],info);
}
}solver;
int N,Q;
int date[MAXN];
int date_[MAXN];
void add_edge(int u,int v){
G[u].push_back(v);
G[v].push_back(u);
}
void read(){
scanf("%d",&N);
for(int i=0;i<N-1;i++){
int u,v;scanf("%d %d",&u,&v);
add_edge(u,v);
}
for(int i=1;i<=N;i++){
scanf("%d",&date[i]);
}
solver.dfs1(1,0,1);
solver.dfs2(1,1);
for(int i=1;i<=N;i++){
date_[solver.map_to_tree[i]]=date[i];
}
solver.build(date_);
}
void work(){
int Q;scanf("%d",&Q);
for(int i=1;i<=Q;i++){
char op[10];
int a,b;
scanf("%s",&op);
scanf("%d %d",&a,&b);
if(op[0]=='C'){
solver.change_num(a,b);
}else if(op[1]=='S'){
int sum=solver.get_sum(a,b);
printf("%d\n",sum);
}else{
int mx=solver.get_max(a,b);
printf("%d\n",mx);
}
}
}
int main(){
freopen("bzoj_1036.in","r",stdin);
freopen("bzoj_1036.out","w",stdout);
read();
work();
return 0;
}
Chenyao2333