[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("%lld\n",out[i]);
    return 0;
}