# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
58843434 |
Practice:
vjudge2 |
1172E
- 24
|
GNU C++11
|
Accepted
|
4554 ms
|
146372 KB
|
2019-08-15 06:31:43 |
2019-08-15 06:31:43 |
|
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read( ){
int x=0,y=1;char ch=' ';
for(;(ch!='-' && (ch>'9' || ch<'0'));ch=getchar( ));
if(ch=='-')y=-1,ch=getchar( );
for(;ch>='0' && ch<='9';ch=getchar( ))x=x*10+ch-48;
return x*y;
}
const int N=4e5+10;
int n,m,cnt;
int c[N],bgn[N],p[N],ans[N],sz[N],s[N],f[N],g[N],fa[N],ch[N][2];
struct node{
int to,nex;
}e[N<<1];
void add(int x,int y){
e[++cnt]=(node){y,bgn[x]};bgn[x]=cnt;
}
struct qry{
int t,x,op;
};
vector<qry>q[N];
int sqr(int x){
return x*x;
}
int nrt(int x){
return ch[fa[x]][0]==x || ch[fa[x]][1]==x;
}
int chk(int x){
return ch[fa[x]][1]==x;
}
void pushup(int x){
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+s[x]+1;
f[x]=sqr(sz[ch[x][0]])+sqr(sz[ch[x][1]])+g[x];
}
void rotate(int x){
int y=fa[x],z=fa[y],k=chk(x);
ch[y][k]=ch[x][k^1];fa[ch[x][k^1]]=y;
if(nrt(y))ch[z][chk(y)]=x;fa[x]=z;
ch[x][k^1]=y;fa[y]=x;
pushup(y);
}
void splay(int x){
while(nrt(x)){
int y=fa[x];
if(nrt(y)){
if(chk(x)==chk(y))rotate(y);
else rotate(x);
}
rotate(x);
}
pushup(x);
}
void access(int x){
for(int y=0;x;y=x,x=fa[x]){
splay(x);
s[x]+=sz[ch[x][1]];g[x]+=sqr(sz[ch[x][1]]);
ch[x][1]=y;
s[x]-=sz[y];g[x]-=sqr(sz[y]);
pushup(x);
}
}
void link(int x,int y){
access(y);splay(y);splay(x);fa[x]=y;
s[y]+=sz[x];g[y]+=sqr(sz[x]);
pushup(y);
}
void cut(int x,int y){
access(y);splay(y);splay(x);fa[x]=0;
s[y]-=sz[x];g[y]-=sqr(sz[x]);
pushup(y);
}
int fndrt(int x){
access(x);splay(x);
while(ch[x][0]){
x=ch[x][0];
}
splay(x);
return x;
}
void dfs(int x){
for(register int i=bgn[x];i;i=e[i].nex){
int y=e[i].to;if(y==p[x])continue;
p[y]=x;dfs(y);
}
}
signed main( ){
int x,y,z,k;
n=read( );m=read( );
for(register int i=1;i<=n;++i)c[i]=read( );
for(register int i=1;i<n;++i){
x=read( );y=read( );add(x,y);add(y,x);
}
dfs(1);p[1]=n+1;
for(register int i=1;i<=n+1;++i)sz[i]=1;
for(register int i=1;i<=n;++i)link(i,p[i]);
for(register int i=1;i<=n;++i)
q[c[i]].push_back((qry){0,i,0});
for(register int i=1;i<=m;++i){
x=read( );y=read( );
q[c[x]].push_back((qry){i,x,1});
q[y].push_back((qry){i,x,0});
c[x]=y;
}
for(register int i=1;i<=n;++i){
q[c[i]].push_back((qry){m+1,i,1});
}
for(register int i=1;i<=n;++i)
for(register int j=0;j<q[i].size( );++j){
x=q[i][j].x;y=fndrt(p[x]);z=q[i][j].t;
if(q[i][j].op){
splay(x);splay(y);
ans[z]+=f[x]+f[y];
link(x,p[x]);
splay(y);
ans[z]-=f[y];
}
else{
splay(y);
ans[z]+=f[y];
cut(x,p[x]);
splay(x);splay(y);
ans[z]-=f[x]+f[y];
}
}
for(register int i=1;i<=m;++i)ans[i]+=ans[i-1];
for(register int i=0;i<=m;++i)printf("%lld\n",ans[i]);
return 0;
}
Click to see test details