题目大意:
对一颗树上进行路径加减,然后询问单点的值。
思路分析:
简单的树链剖分模板题。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #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[root[y]])swap(x,y); update(1,1,n,w[root[x]],w[x],val); x=pre[root[x]]; } if(dep[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; }
Hdu 3699 Aragorn's Story (树链剖分),布布扣,bubuko.com
Hdu 3699 Aragorn's Story (树链剖分)
原文:http://blog.csdn.net/u010709592/article/details/38713067