#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
int readint(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll ans;
int n;
int ch[100005][2],fa[100005],siz[100005],val[100005],rev[100005];
ll c[100005];
vector<pii> v;
int lowbit(int x){return x&(-x);}
void add(int x,int k){for(;x<=n;x+=lowbit(x))c[x]+=k;}
ll ask(int x){ll ret=0;for(;x;x-=lowbit(x))ret+=c[x];return ret;}
bool nroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
bool son(int x){return ch[fa[x]][1]==x;}
void reverse(int x){rev[x]^=1,swap(ch[x][0],ch[x][1]);}
void pushdown(int x){if(rev[x])reverse(ch[x][0]),reverse(ch[x][1]),rev[x]=0;}
void update(int x){siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];}
void rotate(int x){
int y=fa[x],z=fa[y],k=son(x),w=ch[x][!k];
if(nroot(y)) ch[z][son(y)]=x;
ch[x][!k]=y,ch[y][k]=w;
if(w) fa[w]=y;
fa[y]=x,fa[x]=z;
if(!nroot(x)) val[x]=val[y];
update(y),update(x);
}
void pushall(int x){
if(nroot(x)) pushall(fa[x]);
pushdown(x);
}
void splay(int x){
pushall(x);
while(nroot(x)){
int y=fa[x];
if(nroot(y)) rotate(son(x)==son(y)?y:x);
rotate(x);
}
}
void access(int x,int k=0){
for(int y=0;x;x=fa[y=x]){
splay(x);
val[ch[x][1]]=val[x],ch[x][1]=y;
update(x);
if(k) ans+=1ll*(siz[x]-siz[ch[x][1]])*ask(val[x]-1);
if(k) add(val[x],siz[x]-siz[ch[x][1]]),v.push_back(mp(val[x],siz[x]-siz[ch[x][1]]));
if(k) val[x]=k;
}
}
void makeroot(int x){access(x); splay(x); reverse(x);}
int main(){
n=readint();
for(int i=1;i<=n;i++) val[i]=readint();
for(int i=1;i<=n;i++) siz[i]=1;
int x,y;
for(int i=1;i<=n-1;i++){
x=readint(); y=readint();
ans=0;
// cout<<"###########################"<<endl;
// for(int j=1;j<=n;j++) cout<<j<<' '<<fa[j]<<' '<<ch[j][0]<<' '<<ch[j][1]<<' '<<val[j]<<' '<<siz[j]<<endl;
// cout<<"###########################"<<endl;
access(x,val[y]);
printf("%lld\n",ans);
fa[y]=x;
for(int j=0;j<v.size();j++) add(v[j].fi,-v[j].se);
v.clear();
}
return 0;
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v.size();j++) add(v[j].fi,-v[j].se);
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
