이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;
//#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
typedef long long ll;
const int N=1e5+7,lg=20;
int n,c[N],a[N],b[N],h[N],p[N],x[N],fen[N],sp[N][lg];
pair<int,int>com[N];
ll ans[N];
vector<pair<int,int>>vec;
void upd(int i,int x){
for(;i<N;i+=i&(-i)){
fen[i]+=x;
}
}
int get(int i){
int ans=0;
for(;i;i-=i&(-i)){
ans+=fen[i];
}
return ans;
}
int lca(int u,int v){
int f=v;
for(int i=lg-1;i>=0;i--){
if(h[sp[u][i]]>=h[v]){
u=sp[u][i];
}
if(h[sp[v][i]]>=h[u]){
v=sp[v][i];
}
}
for(int i=lg-1;i>=0;i--){
if(sp[u][i]!=sp[v][i]){
u=sp[u][i];
v=sp[v][i];
}
}
x[v]=f;
return u;
}
int main(){
ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
com[i]=mk(c[i],i);
}
int k=1;
sort(com,com+n+1);
for(int i=1;i<=n;i++){
c[com[i].S]=k;
if(com[i].F!=com[i+1].F)k++;
}
for(int i=0;i<n-1;i++){
cin>>a[i]>>b[i];
p[b[i]]=a[i];
h[b[i]]=h[a[i]]+1;
sp[b[i]][0]=a[i];
}
for(int j=1;j<lg;j++){
for(int i=1;i<=n;i++){
sp[i][j]=sp[sp[i][j-1]][j-1];
}
}
x[1]=1;
for(int i=0;i<n-1;i++){
int u=1;
vec.clear();
while(u!=b[i]){
int v;
if(u==a[i])v=b[i];
else v=lca(a[i],x[u]);
//cout<<u<<" "<<v<<endl;
ll t=h[v]-h[u];
//cout<<get(N-1)-get(c[x[u]])<<endl;
ans[i]+=t*(get(N-1)-get(c[x[u]]));
upd(c[x[u]],t);
vec.pb(mk(u,t));
// x[u]=b[i];
u=v;
}
for(auto [p,q]:vec){
upd(c[x[p]],-q);
x[p]=b[i];
}
x[1]=b[i];
x[b[i]]=b[i];
cout<<ans[i]<<endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |