题目描述
一棵树上有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本身
输入输出格式
输入格式:
输入文件的第一行为一个整数n,表示节点的个数。
接下来n – 1行,每行2个整数a和b,表示节点a和节点b之间有一条边相连。
接下来一行n个整数,第i个整数wi表示节点i的权值。
接下来1行,为一个整数q,表示操作的总数。
接下来q行,每行一个操作,以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
输出格式:
对于每个“QMAX”或者“QSUM”的操作,每行输出一个整数表示要求输出的结果。
输入输出样例
输入样例#1:
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
输出样例#1:
4
1
2
2
10
6
5
6
5
16
说明
对于100%的数据,保证1<=n<=30000,0<=q<=200000;中途操作中保证每个节点的权值w在-30000到30000之间。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int N=100005;
int n,m,r,p,tot,dcnt,q;
int w[N],head[N*2],mp[N];
struct NODE{
int to,nex;
}ed[N*2];
struct node{
int fa,son,sz,dep,top,s,e;
}tr[N];//树链剖分
struct Segtree{
int l,r;
int sum,lazy,maxx;
}tree[4*N];
inline void addedge(int x,int y){
++tot;
ed[tot].nex=head[x];
head[x]=tot;
ed[tot].to=y;
}
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return f*x;
}
void dfs1(int u){
tr[u].sz=1;
for(int i=head[u];i;i=ed[i].nex)
if(ed[i].to!=tr[u].fa){
tr[ed[i].to].fa=u;
tr[ed[i].to].dep=tr[u].dep+1;
dfs1(ed[i].to);
tr[u].sz+=tr[ed[i].to].sz;
if(tr[ed[i].to].sz>tr[tr[u].son].sz){
tr[u].son=ed[i].to;
}
}
}
void dfs2(int u,int top){
tr[u].top=top;
tr[u].s=++dcnt;
mp[dcnt]=u;
if(tr[u].son){
dfs2(tr[u].son,top);
for(int i=head[u];i;i=ed[i].nex)
if(ed[i].to!=tr[u].fa&&ed[i].to!=tr[u].son)
dfs2(ed[i].to,ed[i].to);
}
tr[u].e=dcnt;
}
inline void update(int b){
tree[b].sum=tree[b*2].sum+tree[b*2+1].sum;
tree[b].maxx=max(tree[b*2].maxx,tree[b*2+1].maxx);
}
void build(int b,int l,int r){
tree[b].l=l;
tree[b].r=r;
if(l==r){
tree[b].sum=tree[b].maxx=w[mp[l]];
return ;
}
int mid=l+r>>1;
build(b*2,l,mid);
build(b*2+1,mid+1,r);
update(b);
}
int qsum(int id,int l,int r)
{
if(tree[id].l>r || tree[id].r<l)return 0;
if(tree[id].l>=l && tree[id].r<=r)return tree[id].sum;
return (qsum(id*2,l,r)+qsum(id*2+1,l,r));
}
int qmax(int id,int l,int r){
int ans=-1e9;
if(tree[id].l>r || tree[id].r<l)return -1e9;
if(tree[id].l>=l && tree[id].r<=r)return max(ans,tree[id].maxx);
return max(qmax(id*2,l,r),qmax(id*2+1,l,r));
}
int query(int x,int y){
int f1=tr[x].top;
int f2=tr[y].top;
int ans=0;
while(f1!=f2){
if(tr[f1].dep<tr[f2].dep){
swap(x,y);
swap(f1,f2);
}
ans+=qsum(1,tr[f1].s,tr[x].s);
x=tr[f1].fa;
f1=tr[x].top;
}
if(tr[x].dep>tr[y].dep) swap(x,y);
return ans=ans+qsum(1,tr[x].s,tr[y].s);
}
int find(int x,int y){
int f1=tr[x].top;
int f2=tr[y].top;
int ans=-10000000;
while(f1!=f2){
if(tr[f1].dep<tr[f2].dep){
swap(x,y);
swap(f1,f2);
}
ans=max(ans,qmax(1,tr[f1].s,tr[x].s));
x=tr[f1].fa;
f1=tr[x].top;
}
if(tr[x].dep<tr[y].dep)
ans=max(ans,qmax(1,tr[x].s,tr[y].s));
else
ans=max(ans,qmax(1,tr[y].s,tr[x].s));
return ans;
}
void change(int b,int x,int y,int z){
if(y<tree[b].l||x>tree[b].r) return ;
if(tree[b].l==tree[b].r){
tree[b].maxx=z;
tree[b].sum=z;
return ;
}
change(b*2,x,y,z);
change(b*2+1,x,y,z);
update(b);
}
main(){
n=read();
for(int i=1;i<n;i++){
int x,y;
x=read();
y=read();
addedge(x,y);
addedge(y,x);
}
for(int i=1;i<=n;i++) w[i]=read();
dfs1(1);
dfs2(1,1);
build(1,1,n);
q=read();
for(int i=1;i<=q;i++){
string mode;
int x,y,z;
cin>>mode;
if(mode=="QSUM")
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",query(x,y));
}
else if(mode=="CHANGE")
{
scanf("%lld%lld",&x,&z);
change(1,tr[x].s,tr[x].s,z);
}
else if(mode=="QMAX")
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",find(x,y));
}
}
return 0;
}
注意这题输入有负数,求ans要搞好初值