#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
#include "roads.h"
graph g(100005);
int deg[100005];
bool marked[100005];
vector<li> solve_brute(int n, vector<int> u, vector<int> v, vector<int> w)
{
}
vector<li> solve_star(int n, vector<int> w)
{
li tsum=0;
sort(all(w));
for (auto it : w) tsum+=it;
vector<li> ans;
ans.pb(tsum);
while (!w.empty())
{
tsum-=w.back();
w.popb();
ans.pb(tsum);
}
return ans;
}
li dp[100005];
vector<li> solve_line(int n, vector<int> w) //podsetnik: w ima duzinu n-1
{
vector<li> ans;
ans.pb(0);
for (auto it : w) ans.back()+=it;
if (n==2)
{
ans.pb(w[0]);
return ans;
}
dp[0]=w[0];
dp[1]=w[1];
ff(i,2,n-1) dp[i]=w[i]+min(dp[i-2],dp[i-1]);
ans.pb(min(dp[n-3],dp[n-2]));
while ((int)ans.size()<n) ans.pb(0ll);
return ans;
}
vector<int> koji[100005];
vector<li> solve_without_weights(int n, vector<int> u, vector<int> v)
{
ff(i,0,n-1) deg[u[i]]++,deg[v[i]]++;
ff(i,0,n) koji[deg[i]].pb(i);
int cur=0;
vector<li> ans; ans.pb(0);
bff(i,0,n)
{
for (auto p : koji[i])
{
cur++;
marked[p]=true;
for (auto it : g[p]) if (marked[it]) cur--;
}
ans.pb(cur);
}
reverse(all(ans));
return ans;
}
vector<li> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w)
{
bool is_star=true;
ff(i,0,n-1) if (u[i]!=0) is_star=false;
if (is_star) return solve_star(n,w);
bool is_line=true;
ff(i,0,n-1) if (u[i]!=i || v[i]!=i+1) is_line=false;
if (is_line) return solve_line(n,w);
if (n<=2000) return solve_brute(n,u,v,w);
return solve_without_weights(n,u,v);
}
