c/c++语言开发共享[WC2013] 糖果公园

治好了我的树上莫队/带修莫队恐惧症……

对树的分块要求块内的元素都联通，可以参考[scoi 2005]王室联邦的分块做法。对于路径的修改，若已经存在x-y的路径，要转化到x-y的路径（此处所言路径不包含两点的lca），可以发现路径x-y等于路径x-y、路径x-x、路径y-y这三者的对称差（异或？），最后在临时计入点lca(x,y)即可。

然后时模拟时间（修改颜色、撤销修改），当块大小为n^{2/3}时复杂度最优为o(n^{5/3})，（认为q与n同阶）。

#include <bits/stdc++.h> #define ll long long  using namespace std; const int n=1e5+10;  int n,m,q,ccnt,qcnt; int ehd[n],to[n<<1],lst[n<<1],fa[n][20],dep[n]; int top,tot,b,bl[n],stk[n],a[n],v[n],w[n],num[n]; ll ans,out[n]; bool vis[n];  struct timech {int p,x;} c[n]; struct pathch {     int x,y,t,id;     bool operator<(const pathch&d) const {         if(bl[x]!=bl[d.x]) return bl[x]<bl[d.x];         if(bl[y]!=bl[d.y]) return bl[y]<bl[d.y];         return t<d.t;     } } q[n];  void insert(int x,int y) {     static int cnt=0;     to[++cnt]=y,lst[cnt]=ehd[x],ehd[x]=cnt;     to[++cnt]=x,lst[cnt]=ehd[y],ehd[y]=cnt; } void dfs(int x) {     int pre=top;      for(int i=1; (1<<i)<=dep[x]; ++i) fa[x][i]=fa[fa[x][i-1]][i-1];     for(int i=ehd[x]; i; i=lst[i]) if(to[i]!=fa[x][0]) {         int y=to[i]; dep[y]=dep[fa[y][0]=x]+1; dfs(y);         if(top-pre>=b) {             tot++;             do bl[stk[top--]]=tot;             while(top!=pre);         }     }     stk[++top]=x; } int lca(int x,int y) {     if(dep[x]<dep[y]) swap(x,y);     int dif=dep[x]-dep[y];     for(int i=19; ~i; --i) if((dif>>i)&1) x=fa[x][i];     if(x==y) return x;     for(int i=19; ~i; --i) if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];     return fa[x][0]; } void point(int p) {     if(vis[p]) ans-=1ll*v[a[p]]*w[num[a[p]]--];     else ans+=1ll*v[a[p]]*w[++num[a[p]]];     vis[p]^=1; } void time(int t) {     if(vis[c[t].p]) point(c[t].p),swap(c[t].x,a[c[t].p]),point(c[t].p);     else swap(c[t].x,a[c[t].p]); } void path(int x,int y) {     if(dep[x]<dep[y]) swap(x,y);     while(dep[x]>dep[y]) point(x),x=fa[x][0];     while(x!=y) point(x),point(y),x=fa[x][0],y=fa[y][0]; //去掉lca }  int main() {     scanf("%d%d%d",&n,&m,&q); b=pow(n,0.66);     for(int i=1; i<=m; ++i) scanf("%d",v+i);     for(int i=1; i<=n; ++i) scanf("%d",w+i);     for(int x,y,i=n; --i; ) scanf("%d%d",&x,&y),insert(x,y);     for(dfs(1); top; ) bl[stk[top--]]=tot;     for(int i=1; i<=n; ++i) scanf("%d",a+i);     for(int type,i=q; i--; ) {         scanf("%d",&type);         if(type==0) {             ccnt++;             scanf("%d%d",&c[ccnt].p,&c[ccnt].x);         } else {             scanf("%d%d",&q[qcnt].x,&q[qcnt].y);             q[qcnt].t=ccnt;             q[qcnt].id=qcnt;             qcnt++;         }     }     sort(q,q+qcnt);      int x=1,y=1,now=0;     for(int i=0; i<qcnt; ++i) {         path(x,q[i].x); x=q[i].x;         path(y,q[i].y); y=q[i].y;         while(now<q[i].t) time(++now);         while(now>q[i].t) time(now--);         int d=lca(x,y); point(d);         out[q[i].id]=ans;         point(d);     }     for(int i=0; i<qcnt; ++i) printf("%lldn",out[i]);     return 0; }