#include "race.h"
#include <vector>
#include <algorithm>
struct Edge
{
Edge(int v, int w) : dest(v), weight(w) {}
int dest, weight;
};
const int MAXN = 2e5;
const int MAXK = 1e6 + 1;
std::vector<Edge> tree[MAXN];
bool seen[MAXN];
int treeSize[MAXN];
int minRoad[MAXK];
int calcsize(int node)
{
if (seen[node])
return 0;
seen[node] = true;
treeSize[node] = 1;
for (Edge &edge : tree[node])
treeSize[node] += calcsize(edge.dest);
seen[node] = false;
return treeSize[node];
}
int findcentr(int node, int tsize)
{
seen[node] = true;
int maxSub = tsize - treeSize[node];
for (Edge &edge : tree[node])
if (!seen[edge.dest])
{
int centr = findcentr(edge.dest, tsize);
if (centr != -1)
{
seen[node] = false;
return centr;
}
maxSub = std::max(maxSub, treeSize[edge.dest]);
}
seen[node] = false;
if (maxSub > tsize / 2)
return -1;
return node;
}
int count(int node, int taken, int dist, int wanted)
{
if (seen[node] || dist > wanted)
return MAXN;
seen[node] = true;
int length = taken + minRoad[wanted - dist];
for (Edge &edge : tree[node])
length = std::min(length, count(edge.dest, taken + 1, dist + edge.weight, wanted));
seen[node] = false;
return length;
}
void mark(int node, int taken, int dist, int wanted)
{
if (seen[node] || dist > wanted)
return;
seen[node] = true;
minRoad[dist] = std::min(minRoad[dist], taken);
for (Edge &edge : tree[node])
mark(edge.dest, taken + 1, dist + edge.weight, wanted);
seen[node] = false;
}
void unmark(int node, int taken, int dist, int wanted)
{
if (seen[node] || dist > wanted)
return;
seen[node] = true;
minRoad[dist] = MAXN;
for (Edge &edge : tree[node])
unmark(edge.dest, taken + 1, dist + edge.weight, wanted);
seen[node] = false;
}
int findpath(int node, int wanted)
{
if (seen[node])
return MAXN;
int s = calcsize(node);
int centroid = findcentr(node, s);
seen[centroid] = true;
int length = MAXN;
minRoad[0] = 0;
for (Edge &edge : tree[centroid])
{
length = std::min(length, count(edge.dest, 1, edge.weight, wanted));
mark(edge.dest, 1, edge.weight, wanted);
}
for (Edge &edge : tree[centroid])
unmark(edge.dest, 1, edge.weight, wanted);
for (Edge &edge : tree[centroid])
length = std::min(length, findpath(edge.dest, wanted));
return length;
}
int best_path(int N, int K, int H[][2], int L[])
{
for (int iEdge = 0; iEdge < N - 1; iEdge++)
{
tree[H[iEdge][0]].emplace_back(H[iEdge][1], L[iEdge]);
tree[H[iEdge][1]].emplace_back(H[iEdge][0], L[iEdge]);
}
std::fill_n(minRoad, K + 1, MAXN);
int length = findpath(0, K);
if (length == MAXN)
return -1;
return length;
}
