| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1316458 | exoworldgd | 트리 (IOI24_tree) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include"tree.h"
#define ll long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
const int N=2e5+5;
int n,anc[N],val[N];
ll sum,ans[N][2],fa[N],num[N],rig[N],w[N];
vector<int>g[N];
pair<ll,int>e[N];
int find(int u){return fa[u]==u?u:fa[u]=find(fa[u]);}
void upd(int k,ll v){ans[k-1][0]+=k*v,ans[k-1][1]+=-v;}
void con(int u,int v,ll c){
u=find(u),v=find(v);
if(u^v)upd(num[u],rig[u]-c),upd(num[v],rig[v]-c),num[v]+=num[u],rig[v]=c,fa[u]=v;
}
ll qry(int l,int r){
int k=r/l;
return(k>n?0:l*ans[k][0]+r*ans[k][1])+l*sum;
}
void init(vector<int>a,vector<int>b){
n=a.size(),sum=0;
for(int i=0;i<n;i++)anc[i]=a[i],w[i]=b[i],g[i].clear();
for(int i=1;i<n;i++)g[anc[i]].push_back(i);
for(int i=0;i<n;i++)if(g[i].empty())sum+=w[i];
for(int i=0;i<n;i++)fa[i]=i,ans[i][0]=ans[i][1]=0;
for(int i=0;i<n;i++)e[i]={w[i],i};
sort(e,e+n,greater<pair<ll,int>>());
for(int i=0;i<n;i++)num[i]=1,rig[i]=e[0].first,val[i]=0;
for(int i=0;i<n;i++){
auto t=e[i];
if(!t.first)break;
int u=t.second;val[u]=1;
if(anc[u]>=0&&val[anc[u]])con(u,anc[u],t.first);
for(int v:g[u])con(v,u,t.first);
int v=find(u);
if(rig[v]^t.first)upd(num[v],rig[v]-t.first);
num[v]--,rig[v]=t.first;
}
for(int i=0;i<n;i++)ans[i][1]+=ans[i][0];
for(int i=n-2;i;i--)ans[i][0]+=ans[i+1][0],ans[i][1]+=ans[i+1][1];
}
vector<ll>tree(vector<int>a,vector<int>b,vector<int>l,vector<int>r){
init(a,b);
vector<ll>res(l.size());
for(int i=0;i<(int)l.size();i++)res[i]=qry(l[i],r[i]);
return res;
}