?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
121462531 |
Practice: luogu_bot1 |
1172E - 24 | GNU C++11 | Accepted | 2900 ms | 132856 KB | 2021-07-06 12:14:37 | 2021-07-06 12:14:37 |
#include<vector> #include<cstdio> #define pb push_back #define ll long long using namespace std; const int N=1e6; vector<int>cx[N],cy[N],cz[N]; int fa[N],fir[N],nxt[N],to[N],cnt=0,n,m,col[N],ch[N][2],f[N],sz[N],sz1[N]; ll sz2[N],dt[N],ans=0; ll P(int a) { return 1ll*a*a; } void add(int a,int b) { nxt[++cnt]=fir[a]; to[cnt]=b; fir[a]=cnt; } void adda(int a,int b,int c,int d) { cx[a].pb(b); cy[a].pb(c); cz[a].pb(d); } void DFS(int u) {//cout<<"*"<<u<<" "<<fa[u]<<"\n"; for(int i=fir[u];i;i=nxt[i]) if(fa[u]!=to[i]) fa[to[i]]=u,DFS(to[i]); } bool isrt(int x) { return (ch[f[x]][0]!=x)&(ch[f[x]][1]!=x); } void pushup(int x) { sz[x]=sz1[x]+sz[ch[x][0]]+sz[ch[x][1]]+1; } bool son(int x) { return x==ch[f[x]][1]; } void rotate(int x) { int a=f[x],b=f[a],c=son(x),d=son(a),e=ch[x][!c]; if(!isrt(a)) ch[b][d]=x;ch[x][!c]=a;ch[a][c]=e; if(e) f[e]=a;f[a]=x;f[x]=b; pushup(a); } void splay(int x) { int b,c; while(!isrt(x)) { b=f[x];c=f[b]; if(!isrt(b)) { if(son(b)==son(x)) rotate(b); else rotate(x); } rotate(x); } pushup(x); } void access(int x) { for(int y=0;x;y=x,x=f[x]) { splay(x); sz1[x]+=sz[ch[x][1]]-sz[y]; sz2[x]+=P(sz[ch[x][1]])-P(sz[y]); ch[x][1]=y; pushup(x); } } int getroot(int x) { access(x);splay(x); while(ch[x][0]) x=ch[x][0]; splay(x); return x; } void link(int u) { int v=fa[u]; splay(u); ans-=P(sz[ch[u][1]]); ans-=sz2[u]; int w=getroot(v); access(u);splay(w); ans-=P(sz[ch[w][1]]); f[u]=v; splay(v); sz1[v]+=sz[u];sz2[v]+= P(sz[u]); pushup(v); access(u);splay(w); ans+=P(sz[ch[w][1]]); } void cut(int u) { int v=fa[u]; access(u); ans+=sz2[u]; int w=getroot(v); access(u);splay(w); ans-=P(sz[ch[w][1]]); splay(u); ch[u][0]=f[ch[u][0]]=0; pushup(u);splay(w); ans+=P(sz[ch[w][1]]); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&col[i]),adda(col[i],i,1,0); for(int i=1,u,v;i<n;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } for(int i=1;i<=n+1;i++) sz[i]=1; fa[1]=n+1; DFS(1); for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y); adda(col[x],x,-1,i); adda(col[x]=y,x,1,i); } ll las=1ll*n*n; for(int i=1;i<=n;i++) link(i); for(int i=1;i<=n;i++) { for(int j=0;j<cx[i].size();j++) { int x=cx[i][j],y=cy[i][j],z=cz[i][j]; if(y==-1) link(x); else cut(x); dt[z]-=ans-las; las=ans; } for(int j=cx[i].size()-1;j>=0;j--){ int x=cx[i][j],y=cy[i][j],z=cz[i][j]; if(y==-1) cut(x); else link(x); } las=ans; } printf("%lld\n",ans=dt[0]); for(int i=1;i<=m;i++) printf("%lld\n",ans+=dt[i]); return 0; }
?
?
?
?