Description
一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成
一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I
II. 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 4Sample Output
4
1
2
2
10
6
5
6
5
16
【题意】
给出一棵树，每个点有一个权值，要求三种操作：1.修改某个点的权值，2.询问x到y路径上各点的权值最大值，3.询问x到y路径上各点的权值之和。
【分析】
树链剖分+线段树维护。这题维护的是点的值。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 30010
#define INF 0xfffffff struct node
{
int x,y,next;
}t[*Maxn];int len=; int first[Maxn],fa[Maxn],dep[Maxn],top[Maxn],w[Maxn],size[Maxn],son[Maxn];
int wl=; struct nnode
{
int l,r,lc,rc,mx,sum;
}tr[*Maxn];int tl=; int mymax(int x,int y) {return x>y?x:y;} void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
} void dfs1(int x,int f)
{
dep[x]=dep[f]+;
size[x]=;fa[x]=f;son[x]=;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
{
dfs1(t[i].y,x);
size[x]+=size[t[i].y];
if(size[t[i].y]>size[son[x]]) son[x]=t[i].y;
}
} void dfs2(int x,int tp)
{
top[x]=tp;w[x]=++wl;
if(size[x]!=) dfs2(son[x],tp);
for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa[x]&&t[i].y!=son[x])
{
dfs2(t[i].y,t[i].y);
}
} int build(int l,int r)
{
int x=++tl;
tr[x].l=l;tr[x].r=r;tr[x].mx=-INF;tr[x].sum=;
if(l!=r)
{
int mid=(l+r)>>;
tr[x].lc=build(l,mid);
tr[x].rc=build(mid+,r);
}
return x;
} void change(int x,int y,int z)
{
if(tr[x].l==tr[x].r)
{
tr[x].mx=tr[x].sum=z;
return;
}
int mid=(tr[x].l+tr[x].r)>>;
if(y<=mid) change(tr[x].lc,y,z);
else change(tr[x].rc,y,z);
tr[x].mx=mymax(tr[tr[x].lc].mx,tr[tr[x].rc].mx);
tr[x].sum=tr[tr[x].lc].sum+tr[tr[x].rc].sum;
} int queryt(int x,int l,int r,bool p)
{
if(tr[x].l==l&&tr[x].r==r)
{
if(p) return tr[x].mx;
return tr[x].sum;
}
int mid=(tr[x].l+tr[x].r)>>;
if(r<=mid) return queryt(tr[x].lc,l,r,p);
else if(l>mid) return queryt(tr[x].rc,l,r,p);
if(p) return mymax(queryt(tr[x].lc,l,mid,p),queryt(tr[x].rc,mid+,r,p));
return queryt(tr[x].lc,l,mid,p)+queryt(tr[x].rc,mid+,r,p);
} int query(int x,int y,bool p)
{
int f1=top[x],f2=top[y];
int ans=;
if(p) ans=-INF;
while(f1!=f2)
{
if(dep[f1]<dep[f2])
{
swap(f1,f2);
swap(x,y);
}
if(p) ans=mymax(ans,queryt(,w[f1],w[x],p));
else ans+=queryt(,w[f1],w[x],p);
x=fa[f1];
f1=top[x];
}
if(dep[x]<dep[y]) swap(x,y);
if(p) ans=mymax(ans,queryt(,w[y],w[x],p));
else ans+=queryt(,w[y],w[x],p);
return ans;
} int main()
{
int n;
scanf("%d",&n);
memset(first,,sizeof(first));
for(int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
dep[]=;size[]=;
dfs1(,);
dfs2(,);
build(,n);
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
change(,w[i],x);
}
int m;
char s[];
scanf("%d",&m);
while(m--)
{
int x,y;
scanf("%s%d%d",s,&x,&y);
if(s[]=='C')
{
change(,w[x],y);
}
else if(s[]=='S')
{
printf("%d\n",query(x,y,));
}
else
{
printf("%d\n",query(x,y,));
}
}
return ;
}
[BZOJ1036]
2016-05-10 16:54:19
