<题目链接>
题目大意：
给定一颗带点权的树，进行两种操作，一是给定树上一段路径，对其上每个点的点权增加或者减少一个数，二是对某个编号点的点权进行查询。
解题分析：
树链剖分的模板题，还不会树链剖分可以看这里 >>>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Lson l,mid,rt<<1
#define Rson mid+1,r,rt<<1|1
using namespace std;
const int M = 5e4+;
int head[M],sz[M],son[M],f[M],tid[M],rnk[M],dep[M],top[M];
int tot,cnt,n,m,q,a[M],pos,ans;
//sz[]数组，用来保存以x为根的子树节点个数
//top[]数组，用来保存当前节点的所在链的链首
//son[]数组，用来保存重儿子
//dep[]数组，用来保存当前节点的深度
//f[]数组，用来保存当前节点的父亲
//tid[]数组，用来保存树中每个节点剖分后的新编号
//rnk[]数组，线段树中编号对应的原节点编号
struct edge{
int v,next;
}e[M<<];
struct tree
{
int sum,lazy,l,r;
}tree[M<<];
void init(){
tot=cnt=;
memset(head,-,sizeof(head));
}
void add(int u,int v){
e[++cnt].v=v;e[cnt].next=head[u];
head[u]=cnt;
} void dfs1(int u,int fa,int d){
sz[u]=,son[u]=-,f[u]=fa,dep[u]=d;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].v;
if(v==fa) continue;
dfs1(v,u,d+); //继续向下递归
sz[u]+=sz[v];
if(son[u]==-||sz[v]>sz[son[u]]) son[u]=v; //找到该节点的重儿子
}
return ;
} void dfs2(int u,int t){
tid[u]=++tot; //id记录该节点重新编号后的序号
rnk[tot]=u; //线段树中编号对应的原节点编号
top[u]=t; //记录下该节点所在重链的链首
if(son[u]==-) return;
dfs2(son[u],t); //将重边连成重链
for(int i=head[u];~i;i=e[i].next){
int v=e[i].v;
if(v==f[u]||v==son[u]) continue;
dfs2(v,v); //找出以轻儿子为链首的重链
}
return;
}
void Pushup(int rt){
tree[rt].sum=tree[rt<<].sum+tree[rt<<|].sum;
} void Pushdown(int rt){
if(tree[rt].lazy){
int v=tree[rt].lazy;
tree[rt].lazy=;
tree[rt<<].lazy+=v;
tree[rt<<|].lazy+=v;
tree[rt<<].sum+=v*(tree[rt<<].r-tree[rt<<].l+);
tree[rt<<|].sum+=v*(tree[rt<<|].r-tree[rt<<|].l+);
}
} void build(int l,int r,int rt){
tree[rt].l=l;tree[rt].r=r;tree[rt].lazy=;
if(l==r){
tree[rt].sum=a[rnk[l]];
return;
}
int mid=(l+r)>>;
build(Lson);
build(Rson);
Pushup(rt);
}
void update(int L,int R,int l,int r,int rt,int v){
if(L<=l&&r<=R){
tree[rt].lazy+=v;
tree[rt].sum+=v*(r-l+);
return ;
}
Pushdown(rt);
int mid=(l+r)>>;
if(L<=mid) update(L,R,Lson,v);
if(R>mid) update(L,R,Rson,v);
Pushup(rt);
}
void query(int l,int r,int rt){
if(l==r){
ans=tree[rt].sum;
return ;
}
Pushdown(rt);
int mid=(l+r)>>;
if(pos<=mid) query(Lson);
if(pos>mid) query(Rson);
return;
} void updates(int x,int y,int v){
int fx=top[x],fy=top[y]; //x,y所在重链的链首
while(fx!=fy){//如果这两个点不在一条重链上则一直向上跳，并且不断更新
if(dep[fx]>dep[fy]){ //fx节点深度更深
update(tid[fx],tid[x],,n,,v); //更新这一连续区间时，要用该节点在线段树中的编号
x=f[fx],fx=top[x]; //从这条重链爬到父节点所在重链的链首上去
}
else{ //同理
update(tid[fy],tid[y],,n,,v);
y=f[fy],fy=top[y];
}
}
if(dep[x]<dep[y]) //在一条重链中时，直接在线段树中将这一段连续的区间更新
update(tid[x],tid[y],,n,,v);
else
update(tid[y],tid[x],,n,,v);
} int main(){
while(~scanf("%d%d%d",&n,&m,&q)){
init();
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u); //链式前向星存下该无向图
}
dfs1(,-,);
dfs2(,);
build(,n,);
while(q--){
char c[];
int c1,c2,k;
scanf("%s",c);
if(c[]=='I'||c[]=='D'){
scanf("%d%d%d",&c1,&c2,&k);
if(c[]=='D') k*=-;
updates(c1,c2,k);
}
else{
scanf("%d",&c1);
pos=tid[c1]; //pos为c1在线段树中的编号
query(,n,);
printf("%d\n",ans);
}
}
}
return ;
}
2018-09-09