#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;
};
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)
{
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);
}
}
void CalculatePaths(nod* node, nod* block, int k, int &best)
{
vector<path> All_Paths;
vector<vector<path>> Sum(k + 1);
int branch = 0;
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, 1, node->Cost[i], All_Paths);
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:{
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.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() < 2)
continue;
B = Sum[A.sum][1];
}
best = min(best, A.muchi + B.muchi);
}
}
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, NULL, 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;
D_C(vecin, k, desc[vecin->nr], desc, best);
}
}
void add_muchie(nod *A, int B, int cost, vector<nod*> &Tree)
{
nod *C = new nod;
C->nr = B;
A->Ch.push_back(C);
A->Cost.push_back(cost);
C->Ch.push_back(A);
C->Cost.push_back(cost);
Tree[B] = C;
}
int best_path(int n, int k, int H[][2], int L[])
{
int best = inf;
vector<int> desc(n, 0);
vector<nod*> Tree(n, 0);
Tree[0] = new nod;
for (int i = 0; i < n-1; i++)
{
if (H[i][1] < H[i][0])
swap(H[i][1], H[i][0]);
add_muchie(Tree[H[i][0]], H[i][1], L[i], Tree);
}
D_C(Tree[0], k, n, desc, best);
if (best == inf)
return -1;
return best;
}
