/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
const int K_MAX = 1000000;
struct Edge
{
int to;
int len;
};
int aux[K_MAX + 2];
int best_path (int n, int k, int edges[][2], int edgeLen[])
{
vector <Edge> adj[n];
for(int i = 0; i < n - 1; i++)
{
int u = edges[i][0], v = edges[i][1];
adj[u].push_back(Edge{v, edgeLen[i]});
adj[v].push_back(Edge{u, edgeLen[i]});
}
bool deleted[n];
for(int u = 0; u < n; u++)
deleted[u] = false;
int subSize[n];
int parent[n];
vector <int> visited;
function <void (int)> dfs = [&] (int u)
{
visited.push_back(u);
subSize[u] = 1;
for(Edge e : adj[u])
if(e.to != parent[u] && deleted[e.to] == false)
{
parent[e.to] = u;
dfs(e.to);
subSize[u] += subSize[e.to];
}
};
function <int (int)> find_centroid = [&] (int root)
{
parent[root] = -1;
dfs(root);
for(int u : visited)
{
bool isCentroid = true;
for(Edge e : adj[u])
if(e.to != parent[u] && deleted[e.to] == false)
isCentroid &= (subSize[e.to] <= subSize[root] / 2);
if(parent[u] != -1)
isCentroid &= ((subSize[root] - subSize[u]) <= subSize[root] / 2);
if(isCentroid == true)
return u;
}
visited.clear();
return -1;
};
vector <pair <int, int>> minEdges;
function <void (int, int, int)> get_lens = [&] (int u, int depth, int currLen)
{
if(currLen > k)
return;
minEdges.push_back(make_pair(currLen, depth));
for(Edge e : adj[u])
if(e.to != parent[u] && deleted[e.to] == false)
get_lens(e.to, depth + 1, currLen + e.len);
};
for(int i = 1; i <= k; i++)
aux[i] = INT_MAX;
aux[0] = 0;
int answer = INT_MAX;
function <void (int)> solve = [&] (int root)
{
root = find_centroid(root);
parent[root] = -1;
dfs(root);
visited.clear();
vector <int> changed;
for(Edge e : adj[root])
if(deleted[e.to] == false)
{
get_lens(e.to, 1, e.len);
for(pair <int, int> p : minEdges)
{
if(aux[k - p.first] != INT_MAX)
answer = min(answer, aux[k - p.first] + p.second);
}
for(pair <int, int> p : minEdges)
{
aux[p.first] = min(aux[p.first], p.second);
changed.push_back(p.first);
}
minEdges.clear();
}
for(int i : changed)
aux[i] = INT_MAX;
aux[0] = 0;
deleted[root] = true;
for(Edge e : adj[root])
if(deleted[e.to] == false)
solve(e.to);
};
solve(0);
if(answer == INT_MAX)
answer = -1;
return answer;
}
