#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
#include "roads.h"
vector<ll>minimum_closure_costs(int N,vector<int>U,vector<int>V,vector<int>W){
	bool star=1,chain=1,unweighted=1;
	for(int i=0;i<N-1;i++)star&=(U[i]==0),chain&=(U[i]==i&&V[i]==i+1),unweighted&=(W[i]==1);
	if(star){
		sort(W.begin(),W.end(),greater<int>());
		vector<ll>res;
		for(auto x:W)res.push_back(x);
		res.push_back(0);
		for(int i=N-2;i>=0;i--)res[i]+=res[i+1];
		return res;
	}
	if(chain){
		vector<ll>res(N);
		res[0]=accumulate(W.begin(),W.end(),0LL);
		ll cur=0,lst=0;
		for(int i=0;i<W.size();i++){
			swap(cur,lst);
			cur=max(cur+W[i],lst);
		}
		res[1]=res[0]-cur;
		return res;
	}
	if(unweighted){
		vector<ll>res(N);
		vector<vector<int>>adj(N);
		for(int i=0;i<N-1;i++){
			adj[U[i]].push_back(V[i]);
			adj[V[i]].push_back(U[i]);
		}
		vector<int>order(N),vis(N),deg(N);
		iota(order.begin(),order.end(),0);
		sort(order.begin(),order.end(),[&](int i,int j){
			return adj[i].size()>adj[j].size();
		});
		for(int i=0;i<N;i++)sort(adj[i].begin(),adj[i].end(),[&](int j,int k){
			return adj[j].size()>adj[k].size();
		});
		res[0]=N-1;
		for(int k=1;k<N;k++){
			for(auto v:order){
				deg[v]=adj[v].size();
				vis[v]=0;
				if(deg[v]<=k)break;
			}
			function<void(int,int)>dfs=[&](int v,int p){
				vis[v]=1;
				for(auto u:adj[v]){
					if(adj[u].size()<=k)break;
					if(u==p)continue;
					dfs(u,v);
				}
				res[k]+=max(0,deg[v]-k);
				if(deg[p]>k)deg[p]--;
			};
			for(auto v:order){
				if(adj[v].size()<=k)break;
				if(!vis[v])dfs(v,v);
			}
		}
		return res;
	}
	return vector<ll>(N, 0);
}