Description

P4074 [WC2013]糖果公園 - 洛谷 | 計算機科學教育新生態

Solution

樹上莫隊 && 帶修莫隊.

[模板] 各種莫隊

代碼

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<algorithm> #include<set> #include<map> 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 inline typedef 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]<d[b]?a:b;} void sttinit(){dfs(1,0);int l=0;rep(i,1,peu)l2n[i]=(i==(1<<(l+1)))?++l:l;rep(i,1,peu)stt[0][i]=eul[i];rep(i,1,l2n[peu]){repdo(j,peu-(1<<i)+1,1){stt[i][j]=dmin(stt[i-1][j],stt[i-1][j+(1<<(i-1))]);}} } int rmq(int a,int b){if(a>b)swap(a,b);int l=l2n[b-a+1];return dmin(stt[l][a],stt[l][b-(1<<l)+1]); } int lca(int a,int b){return rmq(in[a],in[b]);}int inb[nsz*2]; int col[nsz],now[nsz],get[nsz],cnt[nsz]; ll ans[qsz],ans0=0; int pq=0,pc=0; struct tq{int l,r,t,id;}q[qsz]; struct tc{int p,f,t;}c[qsz]; bool cmp(tq l,tq r){return inb[l.l]!=inb[r.l]?inb[l.l]<inb[r.l]:inb[l.r]!=inb[r.r]?inb[l.r]<inb[r.r]:l.t<r.t;} void addq(int l,int r){if(in[l]>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)++t,solc(c[t].p,c[t].t);while(t>q[i].t)solc(c[t].p,c[t].f),--t;while(l<q[i].l)solp(seq[l++]);while(l>q[i].l)solp(seq[--l]);while(r<q[i].r)solp(seq[++r]);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<<ans[i]<<'\n';return 0; }

轉載于:https://www.cnblogs.com/ubospica/p/10276897.html

總結

以上是生活随笔為你收集整理的luogu4074-[WC2013]糖果公园的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。