本文共 2036 字，大约阅读时间需要 6 分钟。
树上莫队 && 带修莫队.
#include #include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(register int i=(l);i<=(r);++i)#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)#define il inlinetypedef double db;typedef long long ll;//---------------------------------------const int nsz=1e5+50,msz=1e5+50,qsz=1e5+50;int n,m,nq,v[msz],w[nsz],blk;struct te{int t,pr;}edge[nsz*2];int hd[nsz],pe=1;void adde(int f,int t){edge[++pe]=(te){t,hd[f]};hd[f]=pe;}void adddb(int f,int t){adde(f,t);adde(t,f);}int vis[nsz],eul[nsz*3],peu=0,d[nsz];int in[nsz],out[nsz],seq[nsz*2],ps=0;int l2n[nsz*3],stt[20][nsz*3];void dfs(int p,int fa){ seq[++ps]=p,in[p]=ps; eul[++peu]=p,vis[p]=peu; d[p]=d[fa]+1; for(int i=hd[p],v;i;i=edge[i].pr){ v=edge[i].t; if(v==fa)continue; dfs(v,p); eul[++peu]=p; } seq[++ps]=p,out[p]=ps;}int dmin(int a,int b){return d[a] b)swap(a,b); int l=l2n[b-a+1]; return dmin(stt[l][a],stt[l][b-(1< in[r])swap(l,r); ++pq,q[pq]=(tq){lca(l,r)==l?in[l]:out[l],in[r],pc,pq};}void solp(int p){ if(get[p])ans0-=(ll)w[cnt[col[p]]--]*v[col[p]]; else ans0+=(ll)w[++cnt[col[p]]]*v[col[p]]; get[p]^=1;}void solc(int p,int c){ if(get[p])solp(p),col[p]=c,solp(p); else col[p]=c;}void mo(){ sort(q+1,q+pq+1,cmp); int t=0,l=1,r=0; rep(i,1,pq){ while(t q[i].t)solc(c[t].p,c[t].f),--t; while(l q[i].l)solp(seq[--l]); while(r q[i].r)solp(seq[r--]); int x=seq[l],y=seq[r],lc=lca(x,y); if(x!=lc&&r!=lc)solp(lc),ans[q[i].id]=ans0,solp(lc); else ans[q[i].id]=ans0; }}int main(){ ios::sync_with_stdio(0),cin.tie(0); cin>>n>>m>>nq; rep(i,1,m)cin>>v[i]; rep(i,1,n)cin>>w[i]; int a,b,c; rep(i,1,n-1)cin>>a>>b,adddb(a,b); rep(i,1,n)cin>>col[i],now[i]=col[i]; sttinit(); blk=pow(n,2.0/3); rep(i,1,ps)inb[i]=(i-1)/blk+1; rep(i,1,nq){ cin>>a>>b>>c; if(a==0)::c[++pc]=(tc){b,now[b],c},now[b]=c; else addq(b,c); } mo(); rep(i,1,pq)cout< <<'\n'; return 0;}
转载于:https://www.cnblogs.com/ubospica/p/10276897.html