#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int2 long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
inline int scan()
{
char c = getchar_unlocked();
int x = 0;
while(c<'0'||c>'9')
{
c=getchar_unlocked();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar_unlocked();
}
return x;
}
void phongbeo();
const int inf=1e9;
const int mod2=1e9+9;
const int mod1=998244353;
struct icd
{
long double a;
int b;
};
struct ib
{
int a;
int2 b;
};
struct ic
{
int a,b,c;
};
struct id
{
int a,b,c,d;
};
struct ie
{
int a,b,c,d,e;
};
int2 n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,dem4,l,r,mid,l2,r2,center;
int i,s10,s12,s11;
int kk;
int el=29;
vector<ib> v[100001];
vector<int> v3[100001];
vector<int> v2;
vector<long long> vv;
int depth[100001];
int par[100001];
int a[100001];
int b[100001];
bool cmp(int x,int y)
{
return depth[x]>depth[y];
}
struct Node
{
long long sum;
int cnt,leaf;
Node* c[2];
Node()
{
sum=cnt=0;
c[0]=c[1]=NULL;
}
};
struct Trie
{
Node *root=new Node();
void add(int x,int y)
{
Node* cur=root;
if(x<0)x=0;
for(int i=el; i>=0; --i)
{
cur->cnt+=y;
cur->sum+=1ll*x*y;
int tmp =bit(x,i);
if(cur->c[tmp]==NULL)
cur->c[tmp]=new Node();
cur=cur->c[tmp];
}
cur->sum+=x*y;
cur->cnt+=y;
cur->leaf=x;
}
ib get(int k)
{
Node* cur=root;
int2 s=0;
for(int i=el; i>=0; --i)
{
if(cur->c[0]==NULL)
{
cur=cur->c[1];
}
else
{
if(cur->c[0]->cnt>=k)cur=cur->c[0];
else k-=cur->c[0]->cnt,s+=cur->c[0]->sum,cur=cur->c[1];
}
}
s=s+k*cur->leaf;
return {cur->leaf,s};
}
} t[100001];
void dfs(int x,int y)
{
par[x]=y;
depth[x]=++dem;
for(auto f:v[x])
if(f.a!=y)
{
dfs(f.a,x);
t[x].add(f.b,1);
a[f.a]=f.b;
b[f.a]=f.b;
}
s8=v[x].size();
v3[s8-1].pb(x);
}
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++)
l=U[i-1],r=V[i-1],s2=W[i-1],l++,r++,v[l].pb({r,s2}),v[r].pb({l,s2}),s5+=s2;
dfs(1,0);
vv.pb(s4);
a[1]=b[1]=1e9+1;
for(int i=n-2; i>=1; --i)
{
s11=v3[i].size();
for(auto x:v3[i])
v2.pb(x);
if(s11!=0)
sort(v2.begin(),v2.end(),cmp);
s4=0;
for(auto x:v2)
{
if(x!=1)
t[par[x]].add(a[x],-1);
s10=v[x].size();
ib ss2=t[x].get(s10-i);
s4+=ss2.b;
a[x]=b[x];
if(ss2.a>0)a[x]-=ss2.a;
if(a[x]<0)s4+=a[x];
if(x!=1)
t[par[x]].add(a[x],1);
}
vv.pb(s4);
s4=0;
}
vv.pb(s5);
reverse(vv.begin(),vv.end());
return vv;
}
