#include<bits/stdc++.h>
#include "roads.h"
#define MAXN 100007
using namespace std;
struct edge{
int to,flow,cap,rev;
};
int n,a,b,ans[MAXN];
vector<int> v[MAXN];
int parity[MAXN];
vector<edge> g[MAXN];
int ind[MAXN];
vector<int> toupd[MAXN];
void dfs(int x,int p,int dep){
parity[x]=dep%2;
for(int i=0;i<v[x].size();i++){
if(p==v[x][i])continue;
dfs(v[x][i],x,dep+1);
}
}
int source,sink,flow,maxflow;
void add_edge(int from,int to,int c){
g[from].push_back({to,0,c,int(v[to].size())});
g[to].push_back({to,0,0,int(v[from].size())-1});
}
int vis[MAXN],tim;
int fordfulk(int x,int mins){
if(x==sink)return mins;
vis[x]=tim;
for(int i=0;i<g[x].size();i++){
if(vis[g[x][i].to]==tim)continue;
if(g[x][i].flow<g[x][i].cap){
int curr=fordfulk(g[x][i].to,1);
if(curr!=0){
g[x][i].flow++;
g[g[x][i].to][g[x][i].rev].flow--;
return 1;
}
}
}
return 0;
}
void findflow(){
while(true){
tim++;
flow=fordfulk(source,1);
if(flow==0)break;
maxflow+=flow;
}
}
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-1;i++){
a=U[i-1]; b=V[i-1];
a++; b++;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1,0,0);
for(int i=1;i<=n;i++){
for(int f=2;f<=v[i].size();f++){
toupd[f].push_back(i);
}
}
source=0; sink=n+1;
for(int i=1;i<=n;i++){
if(parity[i]==0){
add_edge(source,i,1);
ind[i]=g[source].size()-1;
for(int f=0;f<v[i].size();f++){
add_edge(i,v[i][f],1);
}
}else{
add_edge(i,sink,1);
ind[i]=g[i].size()-1;
}
}
ans[0]=0;
findflow();
ans[1]=maxflow;
for(int i=2;i<=n-1;i++){
for(int f:toupd[i]){
if(parity[f]==0){
g[source][ind[f]].cap++;
}else{
g[f][ind[f]].cap++;
}
}
findflow();
ans[i]=maxflow;
}
vector<long long> res;
for(int i=0;i<=n-1;i++){
res.push_back(n-1-ans[i]);
}
return res;
}
/*int main(){
vector<long long> s=minimum_closure_costs(5, {0, 0, 0, 2}, {1, 2, 3, 4}, {1, 4, 3, 2});
for(long long i:s)cout<<i<<" ";
return 0;
}*/
