題目大意:
對一顆樹上進行路徑加減,然後詢問單點的值。
思路分析:
簡單的樹鏈剖分模板題。
#include#include #include #include #pragma comment(linker,"/STACk:10240000,10240000") #define maxn 50005 #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e using namespace std; int next[maxn<<1],to[maxn<<1],head[maxn],tot;//臨界表 int pre[maxn],root[maxn],siz[maxn],son[maxn],w[maxn],dep[maxn],id;//原樹的父親 鏈上的根 siz 有最大siz的子樹 重新分配的id 深度 getid中來計數的 int sum[maxn<<2],add[maxn<<2];//線段樹變量 int n; void init() { pre[1]=0; dep[1]=0; tot=0;id=0; memset(head,0,sizeof head); memset(sum,0,sizeof sum); memset(add,0,sizeof add); } void addedge(int u,int v) { tot++; next[tot]=head[u]; to[tot]=v; head[u]=tot; } void dfs(int now) { son[now]=0; siz[now]=1; for(int p =head[now]; p ; p=next[p]) { int t=to[p]; if(t!=pre[now]) { pre[t]=now; dep[t]=dep[now]+1; dfs(t); if(siz[t]>siz[son[now]])son[now]=t; siz[now]+=siz[t]; } } } void getid(int now,int rt) { w[now]=++id; root[now]=rt; if(son[now])getid(son[now],rt); for(int p = head[now] ; p ; p=next[p]) { int t=to[p]; if(t!=son[now]&&t!=pre[now]) getid(t,t); } } void pushdown(int num,int s,int e) { if(add[num]) { int mid=(s+e)>>1; sum[num<<1]+=(mid-s+1)*add[num]; sum[num<<1|1]+=(e-mid)*add[num]; add[num<<1]+=add[num]; add[num<<1|1]+=add[num]; add[num]=0; } } void update(int num,int s,int e,int l,int r,int val) { if(l<=s && r>=e) { sum[num]+=(e-s+1)*val; add[num]+=val; return; } pushdown(num,s,e); int mid=(s+e)>>1; if(l<=mid)update(lson,l,r,val); if(r>mid)update(rson,l,r,val); } int query(int num,int s,int e,int pos) { if(s==e)return sum[num]; pushdown(num,s,e); int mid=(s+e)>>1; if(pos<=mid)return query(lson,pos); else return query(rson,pos); } void work(int x,int y,int val) { while(root[x]!=root[y]) { if(dep[root[x]] dep[y])swap(x,y); update(1,1,n,w[x],w[y],val); } int save[maxn]; int main() { int m,Q; while(scanf("%d%d%d",&n,&m,&Q)!=EOF) { init(); for(int i=1;i<=n;i++) scanf("%d",&save[i]); for(int i=1;i<=m;i++) { int s,e; scanf("%d%d",&s,&e); addedge(s,e); addedge(e,s); } dfs(1); getid(1,1); for(int i=1;i<=n;i++) update(1,1,n,w[i],w[i],save[i]); char str[5]; while(Q--) { scanf("%s",str); if(str[0]=='I') { int a,b,c; scanf("%d%d%d",&a,&b,&c); work(a,b,c); } else if(str[0]=='D') { int a,b,c; scanf("%d%d%d",&a,&b,&c); work(a,b,-c); } else { int a; scanf("%d",&a); printf("%d\n",query(1,1,n,w[a])); } } } return 0; }