莫队：
离线后通过对询问合理排序使得复杂度降低一个$sqrt{n}$。（本身并不需要用块维护东西）
一般情况下分块大小为$sqrt{n}$，以左端点所在块为第一关键字，右端点为第二关键字排序。
然后依次暴力处理询问即可。
带修莫队：
一般情况下分块大小为$n^{frac{2}{3}}$，以左端点所在块为第一关键字，右端点所在块为第二关键字，该询问之前的修改数为第三关键字排序。
然后依次暴力处理询问和修改即可。
树上莫队：
一般情况下用欧拉序把树转成括号序列。（每个点第一次dfs到时加入，最后一次dfs回溯时加入）
然后当成序列做，把加入/删除改成xor即可。
代码（WC2013糖果公园）：
#include<bits/stdc++.h> #define maxn 500005 #define maxm 500005 #define inf 0x7fffffff #define ll long long #define rint register ll #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; ll V[maxn],W[maxn],A[maxn],B[maxn],C[maxn]; ll nxt[maxn<<1],to[maxn<<1],hd[maxn]; ll F[maxn][20],tC[maxn],E[maxn],tot; ll dep[maxn],st[maxn],ed[maxn],totu; ll vis[maxn],num[maxn],ans,cnt,siz; struct node{ll l,r,val,id,res;}Q[maxn],U[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline void addedge(ll u,ll v){ to[++cnt]=v,nxt[cnt]=hd[u],hd[u]=cnt; to[++cnt]=u,nxt[cnt]=hd[v],hd[v]=cnt; } inline void dfs(ll u,ll fa){ E[++E[0]]=u,st[u]=E[0]; dep[u]=dep[fa]+1,F[u][0]=fa; for(ll i=1;i<20;i++) F[u][i]=F[F[u][i-1]][i-1]; for(ll i=hd[u];i;i=nxt[i]){ ll v=to[i]; if(v!=fa) dfs(v,u); } E[++E[0]]=u,ed[u]=E[0]; } inline bool cmp(node a,node b){ if(a.l/siz==b.l/siz && a.r/siz==b.r/siz) return a.val<b.val; else if(a.l/siz==b.l/siz) return a.r/siz<b.r/siz; else return a.l/siz<b.l/siz; } inline bool cmp1(node a,node b){return a.id<b.id;} inline ll lca(ll x,ll y){ if(dep[x]>dep[y]) swap(x,y); for(ll i=19;i>=0;i--) if(dep[F[y][i]]>=dep[x]) y=F[y][i]; if(x==y) return x; for(ll i=19;i>=0;i--) if(F[x][i]!=F[y][i]) x=F[x][i],y=F[y][i]; return F[x][0]; } inline void upd(ll u){ vis[u]^=1; if(vis[u]) ans+=W[++num[C[u]]]*V[C[u]]; else ans-=W[num[C[u]]--]*V[C[u]]; } int main(){ ll n=read(),m=read(),q=read(); for(ll i=1;i<=m;i++) V[i]=read(); for(ll i=1;i<=n;i++) W[i]=read(); for(ll i=1;i<=n-1;i++){ ll u=read(),v=read(); addedge(u,v); } for(ll i=1;i<=n;i++) tC[i]=C[i]=read(); for(ll i=1;i<=q;i++){ ll typ=read(),x=read(),y=read(); if(typ==0) U[++totu].val=x,U[totu].l=tC[x],U[totu].r=y,tC[x]=y; else Q[++tot].l=x,Q[tot].r=y,Q[tot].val=totu,Q[tot].id=tot,Q[tot].res=0; } dfs(1,0),siz=pow(2.0*n,2.0/3.0); for(ll i=1;i<=tot;i++){ ll x=Q[i].l,y=Q[i].r; if(dep[x]>dep[y]) swap(x,y); if(lca(x,y)==x) Q[i].l=st[x],Q[i].r=st[y]; else{ if(st[x]>st[y]) swap(x,y); Q[i].l=ed[x],Q[i].r=st[y]; } } sort(Q+1,Q+1+tot,cmp); for(ll i=1;i<=tot;i++){ ll l=Q[i-1].l,r=Q[i-1].r,p=Q[i-1].val; ll f1=lca(E[Q[i-1].l],E[Q[i-1].r]); if(f1!=E[Q[i-1].l]) upd(f1); while(p<Q[i].val){ ll j=++p; if(l<=st[U[j].val] && r>=st[U[j].val] && r<ed[U[j].val]) upd(U[j].val); if(l<=ed[U[j].val] && r>=ed[U[j].val] && l>st[U[j].val]) upd(U[j].val); C[U[j].val]=U[j].r; if(l<=st[U[j].val] && r>=st[U[j].val] && r<ed[U[j].val]) upd(U[j].val); if(l<=ed[U[j].val] && r>=ed[U[j].val] && l>st[U[j].val]) upd(U[j].val); } while(p>Q[i].val){ ll j=p--; if(l<=st[U[j].val] && r>=st[U[j].val] && r<ed[U[j].val]) upd(U[j].val); if(l<=ed[U[j].val] && r>=ed[U[j].val] && l>st[U[j].val]) upd(U[j].val); C[U[j].val]=U[j].l; if(l<=st[U[j].val] && r>=st[U[j].val] && r<ed[U[j].val]) upd(U[j].val); if(l<=ed[U[j].val] && r>=ed[U[j].val] && l>st[U[j].val]) upd(U[j].val); } while(l<Q[i].l) upd(E[l++]); while(l>Q[i].l) upd(E[--l]); while(r<Q[i].r) upd(E[++r]); while(r>Q[i].r) upd(E[r--]); ll f2=lca(E[Q[i].l],E[Q[i].r]); if(f2!=E[Q[i].l]) upd(f2); Q[i].res=ans; } sort(Q+1,Q+1+tot,cmp1); for(ll i=1;i<=tot;i++) printf("%lld ",Q[i].res); return 0; }