#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
vector<vector<pair<int, int>>> adj;
vector<bool> blocked;
int best = INT32_MAX;
int k;
struct Tree
{
int n = 0;
int centroid = -1;
unordered_map<int, int> subtree;
void spread(int i, int p = -1)
{
n++;
for (auto [c, D] : adj[i])
{
if (c != p && !blocked[c])
{
spread(c, i);
}
}
}
int find_centroid(int i, int p = -1)
{
int subtree_size = 1;
int largest_subtree = 0;
for (auto [c, D] : adj[i])
{
if (c != p && !blocked[c])
{
int sub = find_centroid(c, i);
subtree_size += sub;
largest_subtree = max(largest_subtree, sub);
}
}
if (largest_subtree <= n / 2 && n - subtree_size <= n / 2)
centroid = i;
return subtree[i] = subtree_size;
}
void dfs(int i, unordered_map<int, multiset<int>>& out, int d = 0, int depth = 0, int p = -1)
{
out[d].insert(depth);
int subtree_size = 1;
for (auto [c, D] : adj[i])
{
if (c != p && !blocked[c])
{
dfs(c, out, d + D, depth + 1, i);
}
}
}
vector<int> split()
{
blocked[centroid] = true;
vector<int> out;
for (auto [c, d] : adj[centroid])
{
if (!blocked[c])
out.push_back(c);
}
return out;
}
Tree(int start)
{
spread(start);
find_centroid(start);
assert(centroid != -1);
vector<unordered_map<int, multiset<int>>> seperate;
for (auto [c, d] : adj[centroid])
{
seperate.push_back({});
dfs(c, seperate.back(), d, 1, centroid);
}
unordered_map<int, multiset<int>> all;
all[0].insert(0);
for (auto &child : seperate)
{
for (auto &[a, b] : child)
for (auto x : b)
{
all[a].insert(x);
}
}
for (auto &child : seperate)
{
for (auto &[a, b] : child)
for (auto x : b)
{
all[a].erase(all[a].find(x));
}
for (auto &[a, b] : child)
{
if (b.size() == 0)
continue;
int other = k - a;
if (all[other].size())
{
best = min(best, *all[other].begin() + *b.begin());
}
}
for (auto &[a, b] : child)
for (auto x : b)
{
all[a].insert(x);
}
}
}
};
#ifndef _DEBUG
#include "race.h"
#else
int best_path(int N, int K, int H[][2], int L[]);
#endif
int best_path(int N, int K, int H[][2], int L[])
{
adj.resize(N);
blocked.resize(N);
k = K;
for (int i = 0; i < N - 1; i++)
{
adj[H[i][1]].push_back(pair<int, int>{H[i][0], L[i]});
adj[H[i][0]].push_back(pair<int, int>{H[i][1], L[i]});
}
vector<Tree> subtrees;
subtrees.push_back(Tree(0));
queue<int> todo;
todo.push(0);
while (todo.size())
{
int index = todo.front();
todo.pop();
auto out = subtrees[index].split();
for (auto x : out)
{
Tree new_tree(x);
if (new_tree.n > 1)
{
int new_index = subtrees.size();
todo.push(new_index);
subtrees.push_back(move(new_tree));
}
}
}
if (best == INT32_MAX)
return -1;
return best;
}
#ifdef _DEBUG
#define MAX_N 500000
static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;
inline void my_assert(int e)
{
if (!e)
abort();
}
void read_input()
{
int i;
my_assert(2 == scanf("%d %d", &N, &K));
for (i = 0; i < N - 1; i++)
my_assert(3 == scanf("%d %d %d", &H[i][0], &H[i][1], &L[i]));
my_assert(1 == scanf("%d", &solution));
}
signed main()
{
int ans;
read_input();
ans = best_path(N, K, H, L);
if (ans == solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n", ans, solution);
return 0;
}
#endif
