【GDOI 2016 Day1】第四题 疯狂动物城

题目大意

给定一棵树，每个点x有一个权值a[x]，可以询问从x到y的路径上的S值。 具体的，

S=Σu∈x到y的路径Σu到y的距离i=1a[u]∗i 。 还有修改操作。每一次给点l,l+1,…,r的权值加上delta，这个算一个新的历史版本。 原来没修改的点的权值算历史版本0。 最后，还有一种操作，就是将权值回到历史版本x去。 操作中的x,y要疑惑一下上次输出的答案。

题解

题目就是要求 Σu∈x到lca(x,y)a[u]∗[1+...+(deep[u]+deep[y]−2∗deep[lca])]+Σu∈lca(x,y)到ya[u]∗[1+...+(deep[y]−deep[u]]) 那么对于x到lca(x,y)，我们设对答案的贡献为S1。（除以2先不管） 设T=deep[y]-2*deep[lca] S1=a[i]∗(deep[i]+T)∗(deep[i]+T+1) 那么对于lca(x,y)到y，我们设对答案的贡献为S2。（除以2先不管） 设T=deep[y] S2=a[i]∗(−deep[i]+T)∗(−deep[i]+T+1) 那么我们只要在线段树上维护 a[i],a[i]∗deep[i],a[i]∗deep[i]2 就可以了。 为了方便修改，还要维护 deep[i],deep[i]2 。 然后进行树链剖分。 对了，还有回到第几个历史版本的操作，所以还要套主席树。

如何快捷地建立主席树？

首先，新的历史版本的节点维护的值是由旧历史版本的对应节点维护的值变化而来的。 我认为具体的就是先将旧历史版本的对应节点复制到新历史版本的节点去，然后根据题意修改新历史版本的节点维护的相应值。

树链剖分区间修改

步骤： ①比较deep[top[x]]和deep[top[y]]。 ②如果deep[top[x]]>=deep[top[y]]就对路径x~top[x]进行操作，然后跳x，否则就对路径y~top[y]进行操作，然后跳y。转① ③如果top[x]=top[y]，终止循环，并对路径x~y进行操作。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define N 100010 #define mo 20160501 #define LL long long #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) #define eg(i,x) for(i=head[x];i;i=edge[i].next) using namespace std; struct note{int to,next;};note edge[N*2]; struct sgm{ int ls,rs; LL a,ad,ad2,d,d2,lazy; };sgm tr[N*70]; LL i,j,k,l,n,m,T,temp1,temp2; LL x,y,z,op,lastans; int u,v,sgm_tot,ed; int root[N]; LL head[N],val[N]; LL siz[N],dep[N],top[N],hv[N]; LL dfn[N],tar[N],fa[N][17]; LL tot,XXX,tt,ans; void lb(int x,int y){edge[++tot].to=y;edge[tot].next=head[x];head[x]=tot;} void dfs1(int x){ siz[x]=1; for(int i=head[x];i;i=edge[i].next) if (!dep[edge[i].to]){ dep[edge[i].to]=dep[x]+1; fa[edge[i].to][0]=x; dfs1(edge[i].to); siz[x]+=siz[edge[i].to]; if (!hv[x]||siz[edge[i].to]>siz[hv[x]])hv[x]=edge[i].to; } } void dfs2(int x){ dfn[x]=++XXX;tar[XXX]=x; if (hv[x]) top[hv[x]]=top[x],dfs2(hv[x]); for(int i=head[x];i;i=edge[i].next){ if (edge[i].to!=fa[x][0] && edge[i].to!=hv[x]){ top[edge[i].to]=edge[i].to; dfs2(edge[i].to); } } } LL getlca(LL x,LL y){ if (dep[x]<dep[y]) swap(x,y); int i; fd(i,16,0) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i]; if (x==y) return x; fd(i,16,0) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void update(int ps){ int L=tr[ps].ls,R=tr[ps].rs; tr[ps].a=(tr[L].a+tr[R].a)%mo; tr[ps].ad=(tr[L].ad+tr[R].ad)%mo; tr[ps].ad2=(tr[L].ad2+tr[R].ad2)%mo; tr[ps].d=(tr[L].d+tr[R].d)%mo; tr[ps].d2=(tr[L].d2+tr[R].d2)%mo; } void down(int ps,int l,int r){ if (!tr[ps].lazy) return; if (l==r){ tr[ps].lazy=0; return; } int wz=(l+r)/2,L=tr[ps].ls,R=tr[ps].rs,dt=tr[ps].lazy; tr[++sgm_tot]=tr[L]; tr[sgm_tot].a=(tr[sgm_tot].a+dt*(wz-l+1))%mo; tr[sgm_tot].ad=(tr[sgm_tot].ad+dt*tr[sgm_tot].d)%mo; tr[sgm_tot].ad2=(tr[sgm_tot].ad2+dt*tr[sgm_tot].d2)%mo; tr[sgm_tot].lazy=(tr[sgm_tot].lazy+dt)%mo; tr[ps].ls=sgm_tot; tr[++sgm_tot]=tr[R]; tr[sgm_tot].a=(tr[sgm_tot].a+dt*(r-wz))%mo; tr[sgm_tot].ad=(tr[sgm_tot].ad+dt*tr[sgm_tot].d)%mo; tr[sgm_tot].ad2=(tr[sgm_tot].ad2+dt*tr[sgm_tot].d2)%mo; tr[sgm_tot].lazy=(tr[sgm_tot].lazy+dt)%mo; tr[ps].rs=sgm_tot; tr[ps].lazy=0; } void build(int ps,int l,int r){ if (l==r){ tr[ps].a=val[tar[l]]; tr[ps].ad=(tr[ps].a*dep[tar[l]])%mo; tr[ps].ad2=(tr[ps].ad*dep[tar[l]])%mo; tr[ps].d=dep[tar[l]]; tr[ps].d2=dep[tar[l]]*dep[tar[l]]; return; } int wz=(l+r)/2; tr[ps].ls=++sgm_tot;build(tr[ps].ls,l,wz); tr[ps].rs=++sgm_tot;build(tr[ps].rs,wz+1,r); update(ps); } void insert(int ps,int l,int r,int x,int y,int z){ if (l==x && r==y){ tr[ps].a=(tr[ps].a+(r-l+1)*z)%mo; tr[ps].ad=(tr[ps].ad+z*tr[ps].d)%mo; tr[ps].ad2=(tr[ps].ad2+z*tr[ps].d2)%mo; tr[ps].lazy=(tr[ps].lazy+z)%mo; return; } int wz=(l+r)/2; int pp=0; if (tr[ps].lazy) pp=1; down(ps,l,r); if (y<=wz){ if (!pp) tr[++sgm_tot]=tr[tr[ps].ls],tr[ps].ls=sgm_tot; insert(tr[ps].ls,l,wz,x,y,z); } else if (x>wz){ if (!pp) tr[++sgm_tot]=tr[tr[ps].rs],tr[ps].rs=sgm_tot; insert(tr[ps].rs,wz+1,r,x,y,z); } else{ if (!pp) tr[++sgm_tot]=tr[tr[ps].ls],tr[ps].ls=sgm_tot; insert(tr[ps].ls,l,wz,x,wz,z); if (!pp) tr[++sgm_tot]=tr[tr[ps].rs],tr[ps].rs=sgm_tot; insert(tr[ps].rs,wz+1,r,wz+1,y,z); } update(ps); } void query(int ps,int l,int r,int x,int y,int z){ if (l==x && r==y){ ans=(ans+tr[ps].ad2+(tr[ps].a*(T*T+T)%mo)%mo)%mo; ans=(ans+z*tr[ps].ad*(2*T+1)%mo+mo)%mo; return; } down(ps,l,r); int wz=(l+r)/2; if (y<=wz)query(tr[ps].ls,l,wz,x,y,z);else if (x>wz)query(tr[ps].rs,wz+1,r,x,y,z);else{ query(tr[ps].ls,l,wz,x,wz,z); query(tr[ps].rs,wz+1,r,wz+1,y,z); } } void oper(int x,int y,LL z){ LL lca=getlca(x,y); temp1=dep[y]-2*dep[lca]; temp2=dep[y]; bool pp=0; LL tq=1; while (1){ LL tx=top[x],ty=top[y]; if (dep[tx]<dep[ty]){ swap(x,y); swap(tx,ty); tq=-tq; } if (tx==ty) break; if (tq==-1) T=temp2;else T=temp1; if(z==-1)query(root[ed],1,n,dfn[tx],dfn[x],tq); else insert(root[ed],1,n,dfn[tx],dfn[x],z); x=fa[tx][0]; } if (dfn[x]>dfn[y]) swap(x,y),tq=-tq; if (tq==-1) T=temp1;else T=temp2; if (z==-1) query(root[ed],1,n,dfn[x],dfn[y],-tq); else insert(root[ed],1,n,dfn[x],dfn[y],z); } int main(){ freopen("zootopia.in","r",stdin); freopen("zootopia.out","w",stdout); scanf("%lld%lld",&n,&m); fo(i,1,n-1){ scanf("%lld%lld",&u,&v); lb(u,v);lb(v,u); } dep[1]=1;dfs1(1); top[1]=1;dfs2(1); fo(j,1,16)fo(i,1,n)fa[i][j]=fa[fa[i][j-1]][j-1]; lastans=0; fo(i,1,n) scanf("%lld",&val[i]); root[0]=sgm_tot=1; build(root[0],1,n); ed=0; fo(i,1,m){ scanf("%lld",&op); if (op==1){ scanf("%lld%lld%lld",&x,&y,&z); x^=lastans;y^=lastans; root[++tt]=++sgm_tot; tr[sgm_tot]=tr[root[ed]]; ed=tt; oper(x,y,z); } else if (op==2){ scanf("%lld%lld",&x,&y); x^=lastans;y^=lastans; ans=0; oper(x,y,-1); ans=(ans*10080251)%mo; printf("%lld\n",ans); lastans=ans; } else{ scanf("%lld",&x); x^=lastans; ed=x; } } return 0; }