#include "roads.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 200 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;
int n;
std::vector <std::pair <int,int>> g[MAXN];
bool blR[MAXN][MAXN][2];
llong dpR[MAXN][MAXN][2];
bool blC[MAXN][MAXN][MAXN];
llong dpC[MAXN][MAXN][MAXN];
void firstDFS(int node, int par)
{
for (auto &curr : g[node])
{
if (curr.first == par)
{
std::swap(curr, g[node].back());
g[node].pop_back();
break;
}
}
for (const auto &[u, w] : g[node])
{
firstDFS(u, node);
}
}
llong fRoot(int, int, bool);
llong fChildren(int, int, int);
llong fChildren(int node, int idx, int k, int k2)
{
if (idx == -1)
{
return 0;
}
int u = g[node][idx].first;
int w = g[node][idx].second;
if (blC[u][k][k2])
{
return dpC[u][k][k2];
}
blC[u][k][k2] = true;
dpC[u][k][k2] = INF;
if (k < idx + 1) dpC[u][k][k2] = fChildren(node, idx - 1, k, k2) + fRoot(u, k2 - 1, true);
if (k > 0) dpC[u][k][k2] = std::min(dpC[u][k][k2], fChildren(node, idx - 1, k - 1, k2) + fRoot(u, k2, false) + w);
return dpC[u][k][k2];
}
llong fRoot(int node, int k, bool k2)
{
// if (k == 1) std::cout << "call: " << node << ' ' << g[node].size() << ' ' << k << '\n';
if (g[node].empty())
{
if (k >= g[node].size()) return 0;
return INF;
}
if (blR[node][k][k2])
{
return dpR[node][k][k2];
}
blR[node][k][k2] = true;
dpR[node][k][k2] = fChildren(node, g[node].size() - 1, std::max(0, (int)g[node].size() - k), k + k2);
return dpR[node][k][k2];
}
std::vector <llong> minimum_closure_costs(int N, std::vector <int> U, std::vector <int> V, std::vector <int> W)
{
n = N;
for (int i = 0 ; i < n - 1 ; ++i)
{
g[U[i] + 1].push_back({V[i] + 1, W[i]});
g[V[i] + 1].push_back({U[i] + 1, W[i]});
}
firstDFS(1, 0);
std::vector <llong> ans(n);
for (int i = 0 ; i < n ; ++i)
{
ans[i] = fRoot(1, i, false);
}
return ans;
}
