#include <bits/stdc++.h>
using namespace std;
#define inf 1000*1000*1000
#define ll long long
struct nod{
int nr;
vector<nod*> Ch;
vector<int> Cost;
nod(){nr = 0;}
};
struct path{
int br, sum, muchi;
};
vector<vector<path>> Sum;
void DFS_Descendants(nod *node, nod *p, vector<int> &desc)
{
desc[node->nr] = 0;
for (int i = 0; i < node->Ch.size(); i++)
{
auto vecin = node->Ch[i];
if (vecin == p || vecin == 0)
continue;
DFS_Descendants(vecin, node, desc);
desc[node->nr] += desc[vecin->nr];
}
desc[node->nr]++;
}
nod* Locate_Central(nod *node, nod *p, int size, vector<int> &desc)
{
for (int i = 0; i < node->Ch.size(); i++)
{
auto vecin = node->Ch[i];
if (vecin == p || vecin == 0)
continue;
if (desc[vecin->nr] > size/2)
{
desc[node->nr] -= desc[vecin->nr];
desc[vecin->nr] += desc[node->nr];
return Locate_Central(vecin, node, size, desc);
}
}
return node;
}
void DFS_Paths(nod *node, nod *block, int branch, int p, int s, vector<path> &All_Paths, int k)
{
if (s > k)
return;
path A; A.br = branch; A.sum = s; A.muchi = p;
All_Paths.push_back(A);
for (int i = 0; i < node->Ch.size(); i++)
{
auto vecin = node->Ch[i];
if (vecin == block || vecin == 0)
continue;
DFS_Paths(vecin, node, branch, p + 1, s + node->Cost[i], All_Paths, k);
}
}
void CalculatePaths(nod* node, int k, int &best)
{
vector<path> All_Paths;
int branch = 0;
for (int i = 0; i < node->Ch.size(); i++)
{
auto vecin = node->Ch[i];
if (vecin == 0)
continue;
DFS_Paths(vecin, node, branch, 1, node->Cost[i], All_Paths, k);
branch++;
}
for (int i = 0; i < All_Paths.size(); i++)
{
auto A = All_Paths[i];
if (A.sum > k)
continue;
switch(Sum[A.sum].size())
{
case 0:{ Sum[A.sum].push_back(A); break; }
case 1:{
if (A.br == Sum[A.sum][0].br)
{
if (A.muchi < Sum[A.sum][0].muchi)
Sum[A.sum][0] = A;
break;
}
Sum[A.sum].push_back(A);
if (Sum[A.sum][1].muchi < Sum[A.sum][0].muchi)
swap (Sum[A.sum][1], Sum[A.sum][0]);
break; }
default: {
if (A.br == Sum[A.sum][0].br)
{
if (A.muchi < Sum[A.sum][0].muchi)
Sum[A.sum][0] = A;
break;
}
if (A.muchi < Sum[A.sum][1].muchi)
Sum[A.sum][1] = A;
if (Sum[A.sum][1].muchi < Sum[A.sum][0].muchi)
swap (Sum[A.sum][1], Sum[A.sum][0]);
break; }
}
}
for (int i = 0; i < All_Paths.size(); i++)
{
auto A = All_Paths[i];
if (A.sum > k)
continue;
if (A.sum == k)
{
best = min(best, A.muchi);
continue;
}
if (Sum[k - A.sum].size() == 0)
continue;
auto B = Sum[k - A.sum][0];
if (B.br == A.br)
{
if (Sum[B.sum].size() == 1)
continue;
B = Sum[B.sum][1];
}
best = min(best, A.muchi + B.muchi);
}
for (int i = 0; i < All_Paths.size(); i++)
Sum[All_Paths[i].sum].clear();
}
void D_C (nod *root, int k, int size, vector<int> &desc, int &best)
{
if (size == 1)
return;
nod *center;
DFS_Descendants(root, NULL, desc);
center = Locate_Central(root, NULL, size, desc);
CalculatePaths(center, k, best);
for (int i = 0; i < center->Ch.size(); i++)
{
auto vecin = center->Ch[i];
if (vecin == 0)
continue;
for (int j = 0; j < vecin->Ch.size(); j++)
if (vecin->Ch[j] == center)
{ vecin->Ch[j] = NULL; break; }
D_C(vecin, k, desc[vecin->nr], desc, best);
}
}
int best_path(int n, int k, int H[][2], int L[])
{
int best = inf;
vector<int> desc(n, 0);
vector<nod*> Tree(n);
Sum.resize(k + 1);
for (int i = 0; i < n; i++)
{ Tree[i] = new nod; Tree[i]->nr = i; }
for (int i = 0; i < n-1; i++)
{
int A = H[i][0], B = H[i][1];
Tree[A]->Ch.push_back(Tree[B]);
Tree[B]->Ch.push_back(Tree[A]);
Tree[A]->Cost.push_back(L[i]);
Tree[B]->Cost.push_back(L[i]);
}
D_C(Tree[0], k, n, desc, best);
if (best == inf)
return -1;
return best;
}
