树的统计
题目描述
一棵树上有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之间。
分析：
一开始看到以为是个什么很难的数据结构，然后仔细看了一边题面，这不就是个树剖裸题吗？
用结构体写会方便很多，而且因为只有单点修改，所以连下放标记都不需要。我一开始写了个SB特判卡了半天。。。。。。
Code：
#include<bits/stdc++.h>
using namespace std;
const int inf=0x7f7f7f7f;
const int N=3e4+;
int n,m,a[N],head[N],cnt,id,dfn[N],nu[N];
int hson[N],fa[N],dep[N],top[N],size[N];
struct Node{int to,next;}edge[N<<];
struct Seg{
int tot;int mx;
friend Seg operator + (const Seg a,const Seg b)
{
Seg ret;
ret.tot=a.tot+b.tot;
ret.mx=max(a.mx,b.mx);
return ret;
}
}t[N<<];
inline int read()
{
char ch=getchar();int num=;bool flag=false;
while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}
while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}
return flag?-num:num;
}
inline void add(int x,int y)
{
edge[++cnt].to=y;
edge[cnt].next=head[x];
head[x]=cnt;
}
inline void dfs1(int u)
{
size[u]=;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(v==fa[u])continue;
fa[v]=u;dep[v]=dep[u]+;
dfs1(v);size[u]+=size[v];
if(size[v]>size[hson[u]])
hson[u]=v;}
}
inline void dfs2(int u,int now)
{
dfn[++id]=u;nu[u]=id;top[u]=now;
if(!hson[u])return;dfs2(hson[u],now);
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(v==fa[u]||v==hson[u])continue;
dfs2(v,v);}
}
inline void pushup(int rt)
{
t[rt]=t[rt<<]+t[rt<<|];
}
inline void build(int l,int r,int rt)
{
if(l>r)return;
if(l==r){
t[rt].tot=t[rt].mx=a[dfn[l]];
return;}
int mid=(l+r)>>;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
pushup(rt);
}
inline void update(int l,int r,int rt,int L,int R,int C)
{
if(l>R||r<L)return;
if(l==L&&r==R){
t[rt].tot=t[rt].mx=C;
return;}
int mid=(l+r)>>;
update(l,mid,rt<<,L,R,C);
update(mid+,r,rt<<|,L,R,C);
pushup(rt);
}
inline Seg quary(int l,int r,int rt,int L,int R)
{
Seg ret;ret.tot=;ret.mx=-inf;
if(l>R||r<L)return ret;
if(L<=l&&r<=R)return t[rt];
int mid=(l+r)>>;
if(L<=mid)ret=ret+quary(l,mid,rt<<,L,R);
if(R>mid)ret=ret+quary(mid+,r,rt<<|,L,R);
return ret;
}
inline Seg get(int x,int y)
{
int fax=top[x],fay=top[y];
Seg ans;ans.tot=;ans.mx=-inf;
while(fax!=fay){
if(dep[fax]<dep[fay])swap(x,y),swap(fax,fay);
ans=ans+quary(,n,,nu[fax],nu[x]);
x=fa[fax];fax=top[x];}
if(x!=y){
if(dep[x]>dep[y])swap(x,y);}
ans=ans+quary(,n,,nu[x],nu[y]);
return ans;
}
int main()
{
n=read();int x,y;
memset(head,-,sizeof(head));
for(int i=;i<n;i++){
x=read();y=read();
add(x,y);add(y,x);}
for(int i=;i<=n;i++)
a[i]=read();
fa[]=;dep[]=;
dfs1();dfs2(,);
build(,n,);m=read();
for(int i=;i<=m;i++){
char opt[];
scanf("%s",opt);
x=read();y=read();
if(opt[]=='C')
update(,n,,nu[x],nu[x],y);
else {Seg ans=get(x,y);
if(opt[]=='M')printf("%d\n",ans.mx);
else printf("%d\n",ans.tot);}}
return ;
}
