#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include "roads.h"
#define MAXN 100007
using namespace std;
const long long inf=1e9;
int n,a,b,k,sz[MAXN];
long long sum;
vector<int> toadd[MAXN];
vector< pair<int,int> > v[MAXN],g[MAXN];
long long dp[MAXN][2];
int li[MAXN][2],tim;
struct node{
int l,r,cnt;
long long sum;
};
int num;
node tree[100*MAXN];
struct dynamicST{
int root;
void init(){
num++; root=num;
}
void add_node(){
num++;
}
void update(int v,int l,int r,int pos,int val){
if(l==r){
tree[v].cnt+=val;
tree[v].sum+=val*l;
}else{
int mid=(l+r)/2;
if(pos<=mid){
if(tree[v].l==0){
add_node(); tree[v].l=num;
}
update(tree[v].l,l,mid,pos,val);
}else{
if(tree[v].r==0){
add_node(); tree[v].r=num;
}
update(tree[v].r,mid+1,r,pos,val);
}
tree[v].cnt=tree[tree[v].l].cnt+tree[tree[v].r].cnt;
tree[v].sum=tree[tree[v].l].sum+tree[tree[v].r].sum;
}
}
int getcnt(int v,int l,int r,int ll,int rr){
if(v==0)return 0;
if(tree[v].cnt==0)return 0;
if(l==ll and r==rr){
return tree[v].cnt;
}else{
int mid=(l+r)/2;
return getcnt(tree[v].l,l,mid,ll,min(mid,rr)) + getcnt(tree[v].r,mid+1,r,max(mid+1,ll),rr);
}
}
int getkth(int v,int l,int r,int pos){
if(l==r)return l;
int mid=(l+r)/2;
if(tree[tree[v].l].cnt>=pos)return getkth(tree[v].l,l,mid,pos);
else return getkth(tree[v].r,mid+1,r,pos-tree[tree[v].l].cnt);
}
long long getsum(int v,int l,int r,int ll,int rr){
if(v==0)return 0;
if(l==ll and r==rr){
return tree[v].sum;
}else{
int mid=(l+r)/2;
return getsum(tree[v].l,l,mid,ll,min(mid,rr)) + getsum(tree[v].r,mid+1,r,max(ll,mid+1),rr);
}
}
};
struct edges{
dynamicST tree;
void add(int x){
tree.update(tree.root,1,inf,x,1);
}
void rem(int x){
tree.update(tree.root,1,inf,x,-1);
}
int query(long long x){
if(x>inf)x=inf;
return tree.getcnt(tree.root,1,inf,1,x);
}
int getkth(int x){
return tree.getkth(tree.root,1,inf,x);
}
long long getsum(int x){
int val=getkth(x);
long long total=query(val);
return tree.getsum(tree.root,1,inf,1,val)- (total-x)*val;
}
}bonus[MAXN];
long long ff(int x,int p,bool par){
if(li[x][par]==tim)return dp[x][par];
li[x][par]=tim;
dp[x][par]=0;
vector<long long> s;
for(int i=0;i<v[x].size();i++){
if(v[x][i].first==p){
if(par)dp[x][par]+=v[x][i].second;
continue;
}
s.push_back(ff(v[x][i].first,x,true)-ff(v[x][i].first,x,false));
dp[x][par]+=ff(v[x][i].first,x,false);
}
sort(s.begin(),s.end());
int pt=0,pos=-1,cnt=0;
while(pt<s.size() and s[pt]<0){
dp[x][par]+=s[pt]; pt++;
}
if(sz[x]-k-par-pt<=0)return dp[x][par];
int l=pt-1,r=s.size(),tt;
while(l+1<r){
tt=(l+r)/2;
cnt=bonus[x].query(s[tt]);
if(sz[x]-k-par-(tt+1)-cnt<=0){
r=tt;
}else{
l=tt;
}
}
if(r<s.size()){
pos=r;
cnt=bonus[x].query(s[r]);
}
if(pos==-1){
for(int i=pt;i<s.size();i++)dp[x][par]+=s[i];
dp[x][par]+=bonus[x].getsum(sz[x]-k-par-int(s.size()));
return dp[x][par];
}
if(sz[x]-k-par-(pos+1)-cnt==0){
for(int i=pt;i<=pos;i++)dp[x][par]+=s[i];
dp[x][par]+=bonus[x].getsum(sz[x]-k-par-(pos+1));
}else{
for(int i=pt;i<=pos-1;i++)dp[x][par]+=s[i];
dp[x][par]+=bonus[x].getsum(sz[x]-k-par-pos);
}
return dp[x][par];
}
bool in[MAXN];
vector<int> roots;
vector<long long> minimum_closure_costs(int N,vector<int> U,vector<int> V,vector<int> W){
n=N;
for(int i=1;i<=n;i++)bonus[i].tree.init();
for(int i=1;i<=n-1;i++){
a=U[i-1]; b=V[i-1];
a++; b++;
bonus[a].add(W[i-1]);
bonus[b].add(W[i-1]);
g[a].push_back({b,W[i-1]});
g[b].push_back({a,W[i-1]});
sz[a]++; sz[b]++;
sum+=W[i-1];
}
vector<long long> res;
if(g[a].size()==n-1){
sort(W.begin(),W.end());
long long z=0;
for(int i=0;i<=n-1;i++){
res.push_back(z);
if(i<n-1)z+=W[i];
}
reverse(res.begin(),res.end());
return res;
}
for(int i=1;i<=n;i++){
toadd[sz[i]-1].push_back(i);
}
for(int i=n-1;i>=1;i--){
for(int f:toadd[i]){
for(pair<int,int> k:g[f]){
if(!in[k.first])continue;
v[f].push_back({k.first,k.second});
v[k.first].push_back({f,k.second});
bonus[f].rem(k.second);
bonus[k.first].rem(k.second);
}
in[f]=true;
roots.push_back(f);
}
long long curr=0;
tim++; k=i;
for(int f:roots){
if(li[f][0]==tim)continue;
curr+=ff(f,0,0);
}
res.push_back(curr);
}
res.push_back(sum);
reverse(res.begin(),res.end());
return res;
}
/*int main(){
vector<long long> s=minimum_closure_costs(5, {0, 0, 0, 2}, {1, 2, 3, 4}, {1, 4, 3, 2});
vector<long long> s=minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5});
for(long long i:s)cout<<i<<" ";
return 0;
}*/
