hdu3966Aragorn's Story

链接：http://acm.hdu.edu.cn/showproblem.php?pid=3966

题意：给定一棵树，3中操作：A：给u->v的路径上所有点点权+k。B：给u->v的路径上所有点点权-k。C：求节点u的点权。

分析：树链剖分+树状数组维护。

代码：

#include<map> #include<set> #include<cmath> #include<queue> #include<bitset> #include<math.h> #include<vector> #include<string> #include<stdio.h> #include<cstring> #include<iostream> #include<algorithm> #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; const int N=50010; const int mod=998244353; const int MOD1=1000000007; const int MOD2=1000000009; const double EPS=0.00000001; typedef long long ll; const ll MOD=1000000007; const int INF=1000000010; const ll MAX=1ll<<55; const double eps=1e-5; const double inf=~0u>>1; const double pi=acos(-1.0); typedef double db; typedef unsigned int uint; typedef unsigned long long ull; int tot,u[N],v[2*N],pre[2*N]; void add(int x,int y) { v[tot]=y;pre[tot]=u[x];u[x]=tot++; v[tot]=x;pre[tot]=u[y];u[y]=tot++; } int n,fa[N],dep[N],siz[N],son[N],top[N],pos[N]; void dfs1(int x,int y) { siz[x]=1;son[x]=0; dep[x]=dep[y]+1;fa[x]=y; int i,mx=0; for (i=u[x];i!=-1;i=pre[i]) if (v[i]!=y) { dfs1(v[i],x);siz[x]+=siz[v[i]]; if (siz[v[i]]>mx) son[x]=v[i],mx=siz[v[i]]; } } void dfs2(int x,int y) { if (son[y]==x) top[x]=top[y]; else top[x]=x;pos[x]=++tot; if (son[x]) dfs2(son[x],x); for (int i=u[x];i!=-1;i=pre[i]) if (v[i]!=y&&v[i]!=son[x]) dfs2(v[i],x); } ll z,a[N],f[N];char s[5]; void updata(int x,int y,ll z) { for (;x<=n;x+=x&-x) f[x]+=z; for (;y<=n;y+=y&-y) f[y]-=z; } ll get(int x) { ll ret=0; for (;x;x-=x&-x) ret+=f[x]; return ret; } void modify(int x,int y,ll z) { int f1=top[x],f2=top[y]; while (f1!=f2) { if (dep[f1]<dep[f2]) swap(x,y),swap(f1,f2); updata(pos[f1],pos[x]+1,z); x=fa[f1];f1=top[x]; } if (dep[x]<dep[y]) swap(x,y); updata(pos[y],pos[x]+1,z); } int main() { int i,m,q,x,y; while (scanf("%d%d%d", &n, &m, &q)!=EOF) { tot=0;memset(u,-1,sizeof(u)); for (i=1;i<=n;i++) scanf("%I64d", &a[i]); for (i=1;i<=m;i++) scanf("%d%d", &x, &y),add(x,y); memset(f,0,sizeof(f)); dfs1(1,0);tot=0;dfs2(1,0); for (i=1;i<=n;i++) updata(pos[i],pos[i]+1,a[i]); while (q--) { scanf("%s", s); if (s[0]=='I') { scanf("%d%d%I64d", &x, &y, &z);modify(x,y,z); } else if (s[0]=='D') { scanf("%d%d%I64d", &x, &y, &z);modify(x,y,-z); } else { scanf("%d", &x);printf("%I64d\n", get(pos[x])); } } } return 0; }