hdu3966[维护点权]

发表于 | 分类于 ， ， | 阅读数 次

链接:hdu3966[维护点权]

题解

  • 注意仔细读题,维护点权模板题 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long 
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
using namespace std;
const int N=1e5;
int rt[N<<2],lz[N<<2],id[N],top[N],deep[N],size[N],f[N],hson[N];
int nxt[N],w[N],wt[N],head[N],to[N];
int n,m,q,a,b,c,cnt;
char op[2];
inline void adde(int u,int v){nxt[++cnt]=head[u];to[cnt]=v;head[u]=cnt;}
inline void pushup(int o){rt[o]=rt[o<<1]+rt[o<<1|1];}
inline void pushdown(int o,int len){
	if(!lz[o])return ;
	lz[o<<1]+=lz[o];
	lz[o<<1|1]+=lz[o];
	rt[o<<1]+=lz[o]*(len-(len>>1));
	rt[o<<1|1]+=lz[o]*(len>>1);
	lz[o]=0;
}
inline void build(int o,int l,int r){
	lz[o]=0;
	if(l==r){rt[o]=w[l]; return ;}
	int mid=l+r>>1;
	build(lson);
	build(rson);
	pushup(o);
}
inline void update(int o,int l,int r,int L,int R,int x){
	if(L<=l&&R>=r){rt[o]+=x*(r-l+1); lz[o]+=x;return ;}
	int mid=l+r>>1;
	pushdown(o,r-l+1);
	if(L<=mid)update(lson,L,R,x);
	if(R>mid)update(rson,L,R,x);
	pushup(o);
}
inline int query(int o,int l,int r,int x){
	if(l==r)return rt[o];
	pushdown(o,r-l+1);
	int mid=l+r>>1;
	if(x<=mid)return query(lson,x);
	return query(rson,x);
}
inline void dfs1(int x){
	size[x]=1;
	for(int i=head[x];i;i=nxt[i])if(to[i]!=f[x]){
		f[to[i]]=x;
		deep[to[i]]=deep[x]+1;
		dfs1(to[i]);
		size[x]+=size[to[i]];
		if(size[hson[x]]<size[to[i]])hson[x]=to[i];
	}
}
inline void dfs2(int x,int t){
	top[x]=t;id[x]=++cnt;w[cnt]=wt[x];
	if(hson[x])dfs2(hson[x],t);
	for(int i=head[x];i;i=nxt[i])if(hson[x]!=to[i]&&to[i]!=f[x])dfs2(to[i],to[i]);
}
inline void uprange(int x,int y,int k){
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		update(1,1,n,id[top[x]],id[x],k);
		x=f[top[x]];
	}
	if(deep[x]>deep[y])swap(x,y);
	update(1,1,n,id[x],id[y],k);
}
int main(){
	while(~scanf("%d%d%d",&n,&m,&q)){
		//memset(f,-1,sizeof(f));
		memset(head,0,sizeof(head));
		memset(hson,0,sizeof(hson));
		cnt=deep[1]=0;
		rep(i,1,n)scanf("%d",&wt[i]);
		rep(i,2,n){
			scanf("%d%d",&a,&b);
			adde(a,b);adde(b,a);
		}cnt=0;
		dfs1(1);
		dfs2(1,1);
		build(1,1,n);
		while(q--){
			scanf("%s",op);
			if(op[0]=='Q'){scanf("%d",&a);printf("%d\n",query(1,1,n,id[a]));}
			else {
				scanf("%d%d%d",&a,&b,&c);
				if(op[0]=='D')c*=-1;
				uprange(a,b,c);
			}
		}
	}
	return 0;
}