| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1213873 | user736482 | 트리 (IOI24_tree) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll n,ans[1000007][2];
vector<ll>d[200007];
ll moj[200007],sz[200007];
bool czy[200007];
ll fnd(ll x){
if(moj[x]==x)return x;
return moj[x]=fnd(moj[x]);
}
void onion(ll x,ll y,ll c){
x=fnd(x);y=fnd(y);
if(sz[x]>sz[y])swap(x,y);
moj[x]=y;
sz[y]+=sz[x]-!czy[c];
czy[c]=1;
}
void init(vector<int>p,vector<int>w){
n=p.size();
for(ll i=0;i<200007;i++){moj[i]=i;sz[i]=1;}
for(ll i=1;i<n;i++)d[p[i]].pb(i);
for(ll i=0;i<n;i++)if(d[i].empty())ans[1][0]+=2;
ans[1][0]-=n;
ans[1][1]+=n-1;
vector<pair<ll,ll>>v;
for(ll i=0;i<n;i++)if(d[i].size())v.pb({w[i],i});
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
for(auto i : v){
ll pm=0;
ans[max(1LL,sz[fnd(i.ss)]-1)][0]+=sz[fnd(i.ss)];
ans[max(1LL,sz[fnd(i.ss)]-1)][1]--;
vector<ll>ak;
ll aa=sz[fnd(i.ss)];
for(ll j : d[i.ss]){
ans[sz[fnd(j)]][1]--;
ans[sz[fnd(j)]][0]+=sz[fnd(j)];
pm+=sz[fnd(j)];
onion(i.ss,j,i.ss);
}
ans[aa+pm-1][0]+=(-pm-aa+1);
ans[aa+pm-1][1]++;
}
for(ll i=2;i<1000007;i++){
ans[i][0]+=ans[i-1][0];
ans[i][1]+=ans[i-1][1];
}
}
ll query(ll l,ll r){
return ans[r/l][0]*l+ans[r/l][1]*r;
}