树链剖分模板题
把链映射到线段树上 询问的过程中 在一条链上的询问才是有效的 所以有个change操作（不是随意的划分区间）
注意区间连续和离散的区别（点还是边）
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <bits/stdc++.h> #define N 50100 #define FREI freopen("in.txt","r",stdin) #define Mem(a,b) memset(a,b,sizeof(a)) #define lson root<<1 #define rson root<<1|1 #define Mid int mid=(l+r)>>1 using namespace std; vector<int>T[N]; int n,m,k,num[N],siz[N],fa[N],son[N],cnt,f[N],invf[N],dep[N],tp[N],sum[N<<2],ans,mark[N<<2]; /*第一次bfs得到深度，父亲节点，子数大小等信息*/ void dfs1(int u,int father){ //cout<<u<<' '<<father<<endl; dep[u]=dep[father]+1; fa[u]=father; siz[u]++; for(int i=0;i<T[u].size();i++){//auto 有问题？？ int v=T[u][i]; //cout<<v<<endl; if(v!=father){ dfs1(v,u); siz[u]+=siz[v]; if(son[u]==-1||siz[son[u]]<siz[v]) son[u]=v; } } } /*第二次得到节点的新编号 映射和逆映射 还有重链上的顶端的点*/ void dfs2(int u,int top){ tp[u]=top; f[u]=++cnt;//时间戳 invf[f[u]]=u; if(son[u]==-1)//忘了判断条件 return ; dfs2(son[u],top); for(int i=0;i<T[u].size();i++){ int v=T[u][i]; if(v!=son[u]&&v!=fa[u]){ dfs2(v,v); } } } void push_down(int root,int l,int r){ Mid; if(mark[root]){ mark[lson]+=mark[root]; mark[rson]+=mark[root]; sum[lson]+=mark[root]*(mid-l+1); sum[rson]+=mark[root]*(r-mid); mark[root]=0; } } void build(int root,int l,int r){ if(l==r){ sum[root]=num[invf[l]]; return ; } Mid; build(lson,l,mid); build(rson,mid+1,r); } void update(int root,int l,int r,int ql,int qr,int val){ if(l>qr||r<ql) return; if(l>=ql&&r<=qr){ if(l==r) sum[root]+=val*(r-l+1); mark[root]+=val; return ; } Mid; push_down(root,l,r); update(lson,l,mid,ql,qr,val); update(rson,mid+1,r,ql,qr,val); } void query(int root,int l,int r,int ql,int qr){ if(l>qr||r<ql) return; if(l>=ql&&r<=qr){ ans=sum[root]; return ; } Mid; push_down(root,l,r); query(lson,l,mid,ql,qr); query(rson,mid+1,r,ql,qr); } void change(int x,int y,int val){//非常关键的change操作 while(tp[x]!=tp[y]){ if(dep[tp[x]]<dep[tp[y]]) swap(x,y); update(1,1,n,f[tp[x]],f[x],val); x=fa[tp[x]]; } if(dep[x]>dep[y]) swap(x,y); update(1,1,n,f[x],f[y],val); } int main() { //FREI; while(scanf("%d%d%d",&n,&m,&k)!=EOF){ Mem(siz,0); Mem(son,-1); Mem(dep,0); Mem(mark,0);//忘记初始化 cnt=0; for(int i=1;i<=n;i++) scanf("%d",&num[i]); for(int i=1;i<=n;i++) T[i].clear(); for(int i=0;i<m;i++){ int u,v; scanf("%d%d",&u,&v); //cout<<u<<' '<<v<<endl; T[u].push_back(v); T[v].push_back(u); } dfs1(1,1); dfs2(1,1); build(1,1,n);//忘记build了 for(int i=1;i<=k;i++){ char x; scanf("\n%c",&x); if(x=='Q'){ int a; scanf("%d",&a); query(1,1,n,f[a],f[a]); printf("%d\n",ans); } else { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(x=='D') c=-c; change(a,b,c); } } } }
