2460 树的统计
2008年省队选拔赛浙江
时间限制: 2 s 空间限制: 128000 KB 题目等级 : 大师 Master
题目描述 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 Description
输入文件的第一行为一个整数n，表示节点的个数。
接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。
接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。
接下来1行，为一个整数q，表示操作的总数。
接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
输出描述 Output Description
对于每个“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
数据范围及提示 Data Size & Hint
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 300001
using namespace std;
int head[maxn],dep[maxn],fa[maxn],a[maxn];
int pos[maxn],top[maxn],size[maxn],son[maxn];
int tot,n,m,cnt,maxsize,x,y,num;
struct Edge{int next,to;}e[maxn<<];
struct Node{int l,r,max,sum;}tre[maxn<<];
int read(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int max(int a,int b){if(a>b)return a;else return b;}
void Add_Edge(int u,int v){
e[++num].to=v;e[num].next=head[u];head[u]=num;
}
void DFS_First(int now,int pre,int deepth){
dep[now] = deepth; fa[now] = pre; size[now] = ;
for(int i=head[now];i;i=e[i].next){
int v=e[i].to;
if(v!=pre){
DFS_First(v,now,deepth+);
size[now] += size[v];
if(son[now]==-||size[v]>size[son[now]])
son[now]=v;
}
}
}
void Get_Pos(int u,int Top){
int k=;maxsize++;
pos[u]=maxsize;top[u]=Top;
if(!son[u])return;
Get_Pos(son[u],Top);
for(int i=head[u];i;i=e[i].next)
if(dep[e[i].to]>dep[u]&&e[i].to!=son[u])
Get_Pos(e[i].to,e[i].to);
return;
}
void Build(int now,int l,int r){
tre[now].l=l;tre[now].r=r;
if(l==r){
tre[now].sum=tre[now].max=;return ;
}
int mid=(l+r)>>;
Build(now<<,l,mid);Build(now<<|,mid+,r);
tre[now].sum=tre[now<<].sum+tre[now<<|].sum;
tre[now].max=max(tre[now<<].max,tre[now<<|].max); }
void Insert(int now,int poss,int val){
if(tre[now].l==tre[now].r){
tre[now].sum=tre[now].max=val;return;
}
int mid=(tre[now].l+tre[now].r)/;
if(poss<=mid)Insert(now<<,poss,val);
else if(poss>mid)Insert(now<<|,poss,val);
tre[now].sum=tre[now<<].sum+tre[now<<|].sum;
tre[now].max=max(tre[now<<].max,tre[now<<|].max);
}
int QueryMax(int now,int l,int r){
if(l<=tre[now].l&&tre[now].r<=r)return tre[now].max;
int mid=(tre[now].l+tre[now].r)>>,total=-1e9;
if(l<=mid)total=max(total,QueryMax(now<<,l,r));
if(r>mid)total=max(total,QueryMax(now<<|,l,r));
return total;
}
int QuerySum(int now,int l,int r){
if(l<=tre[now].l&&tre[now].r<=r)return tre[now].sum;
int mid=(tre[now].l+tre[now].r)>>,total=;
if(l<=mid)total+=QuerySum(now<<,l,r);
if(r>mid)total+=QuerySum(now<<|,l,r);
return total;
}
int SolveMax(int u,int v){
int ans=-1e9;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
ans=max(ans,QueryMax(,pos[top[u]],pos[u]));
u=fa[top[u]];
}
if(pos[u]>pos[v]) swap(u,v);
ans=max(ans,QueryMax(,pos[u],pos[v]));
return ans;
}
int SolveSum(int u,int v){
int ans=;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
ans+=QuerySum(,pos[top[u]],pos[u]);
u=fa[top[u]];
}
if(pos[u]>pos[v])swap(u,v);
ans+=QuerySum(,pos[u],pos[v]);
return ans;
}
int main(){
n=read();
for(int i=;i<n;i++){
x=read();y=read();
Add_Edge(x,y);Add_Edge(y,x);
}
for(int i=;i<=n;i++) a[i]=read();
DFS_First(,,);
Get_Pos(,);
Build(,,maxsize);
for(int i=;i<=n;i++)
Insert(,pos[i],a[i]);
m=read();char sp[];
while(m--){
scanf("%s",sp);scanf("%d%d",&x,&y);
if(sp[]=='C')a[x]=y,Insert(,pos[x],y);
else{
if(sp[]=='M') printf("%d\n",SolveMax(x,y));
else printf("%d\n",SolveSum(x,y));
}
}
return ;
}