题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3966
题目大意：营地的分布成树型。每个营地都有一些人，每次修改修改一条链上的所有营地的人数，每次查询单个点。
解题思路：
树链剖分基础题。
维护一个sum。
注意轻链修改时，点修改和边修改的不同。
由于树的结构与线段树点的顺序不太相同，因此需要做一个映射数组rank。故在线段树Build的时候，权值是camp[rank[l]]，rank这步的映射在dfs2的时候完成，rank[w[u]]=u;
Query单点u的时候, w[u]是其在线段树中的位置。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include "cstdio" #include "vector" #include "cstring" using namespace std; #define maxn 50005 int camp[maxn],s[maxn],dep[maxn],pos[maxn],son[maxn],top[maxn],fa[maxn],w[maxn],rank[maxn],cnt,n; vector<int> G[maxn]; void dfs1(int u,int pre,int d) { s[u]=1;fa[u]=pre;dep[u]=d; for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(v==pre) continue; dfs1(v,u,d+1); s[u]+=s[v]; if(son[u]!=-1||s[v]>s[son[u]]) son[u]=v; } } void dfs2(int u,int tp) { w[u]=++cnt;top[u]=tp;rank[w[u]]=u; if(son[u]==-1) return; dfs2(son[u],tp); for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(v!=son[u]&&v!=fa[u]) dfs2(v,v); } } //Segment-Tree #define lson l,mid,root<<1 #define rson mid+1,r,root<<1|1 int col[maxn<<2],sum[maxn<<2]; void PushUp(int root) { sum[root]=sum[root<<1]+sum[root<<1|1]; } void Build(int l,int r,int root) { col[root]=0; if(l==r) { sum[root]=camp[rank[l]]; return; } int mid=(l+r)>>1; Build(lson); Build(rson); PushUp(root); } void PushDown(int root,int m) { if(col[root]) { col[root<<1]+=col[root]; col[root<<1|1]+=col[root]; sum[root<<1]+=(m-(m>>1))*col[root]; sum[root<<1|1]+=(m>>1)*col[root]; col[root]=0; } } void Update(int L,int R,int v,int l,int r,int root) { if(L<=l&&r<=R) { col[root]+=v; sum[root]+=(r-l+1)*v; return; } PushDown(root,r-l+1); int mid=(l+r)>>1; if(L<=mid) Update(L,R,v,lson); if(R>mid) Update(L,R,v,rson); PushUp(root); } int Query(int p,int l,int r,int root) { if(l==r) return sum[root]; PushDown(root,r-l+1); int mid=(l+r)>>1,ret=0; if(p<=mid) ret=Query(p,lson); else ret=Query(p,rson); return ret; } void Change(int x,int y,int v) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); Update(w[top[x]],w[x],v,1,n,1); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); Update(w[x],w[y],v,1,n,1);//与边修改不同 } int main() { //freopen("in.txt","r",stdin); int m,p,u,v,c; while(scanf("%d%d%d",&n,&m,&p)!=EOF) { memset(son,-1,sizeof(son)); for(int i=0;i<=n;i++) G[i].clear(); cnt=0; for(int i=1;i<=n;i++) scanf("%d",&camp[i]); for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } dfs1(1,1,1); dfs2(1,1); Build(1,n,1); char cmd[10]; for(int i=1;i<=p;i++) { scanf("%s",&cmd); if(cmd[0]=='I') { scanf("%d%d%d",&u,&v,&c); Change(u,v,c); } if(cmd[0]=='D') { scanf("%d%d%d",&u,&v,&c); Change(u,v,-c); } if(cmd[0]=='Q') { scanf("%d",&c); printf("%d ",Query(w[c],1,n,1)); } } } }
| 11757337 | 2014-09-29 16:51:29 | Accepted | 3966 | 2484MS | 8308K | 3299 B | C++ | Physcal |