#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
#include <random>
struct Key {
int key;
int lazy;
int lazy_v;
Key(int key) : key(key), lazy(0), lazy_v(0) {}
};
struct Mapped {
int a;
Mapped() : a(0) {}
Mapped(int a) : a(a) {}
};
// clang-format off
struct Cmp;
using _Alloc = std::allocator<char>;
using Node_And_It_Traits =
__gnu_pbds::detail::tree_traits<Key, Mapped, Cmp,
__gnu_pbds::null_node_update,
__gnu_pbds::rb_tree_tag, _Alloc>;
using traits_type = Node_And_It_Traits;
typedef __gnu_pbds::detail::rebind_traits<_Alloc, typename traits_type::node>
node_alloc_traits;
using value_type = node_alloc_traits::value_type;
using node_pointer = node_alloc_traits::pointer;
void propagate(traits_type::node &node, int lazy, int lazy_v) {
if (node.m_p_left) {
node.m_p_left->m_value.second.a += lazy_v;
const_cast<Key *>(&node.m_p_left->m_value.first)->key += lazy;
const_cast<Key *>(&node.m_p_left->m_value.first)->lazy += lazy;
const_cast<Key *>(&node.m_p_left->m_value.first)->lazy_v += lazy_v;
}
if (node.m_p_right) {
node.m_p_right->m_value.second.a += lazy_v;
const_cast<Key *>(&node.m_p_right->m_value.first)->key += lazy;
const_cast<Key *>(&node.m_p_right->m_value.first)->lazy += lazy;
const_cast<Key *>(&node.m_p_right->m_value.first)->lazy_v += lazy_v;
}
}
void work_on(Key *key_ptr) {
const constexpr auto offset = offsetof(traits_type::node, m_value.first);
unsigned char *node_u8_ptr =
reinterpret_cast<unsigned char *>(const_cast<Key *>(key_ptr));
traits_type::node *node_ptr = std::launder(
reinterpret_cast<traits_type::node *>(node_u8_ptr - offset));
propagate(*node_ptr, key_ptr->lazy, key_ptr->lazy_v);
key_ptr->lazy = 0;
key_ptr->lazy_v = 0;
}
struct Cmp {
bool operator()(const Key &lhs, const Key &rhs) const {
// This lets you determine which side corresponds to the most recently-inserted value:
// static const void *inserting = nullptr;
// if (!inserting) inserting = (void *)&rhs;
if (lhs.lazy || lhs.lazy_v)
work_on(const_cast<Key *>(&lhs));
if (rhs.lazy || rhs.lazy_v)
work_on(const_cast<Key *>(&rhs));
return lhs.key < rhs.key;
}
};
// clang-format on
struct map : public __gnu_pbds::tree<Key, Mapped, Cmp, __gnu_pbds::rb_tree_tag,
__gnu_pbds::null_node_update> {
using base_type =
__gnu_pbds::tree<Key, Mapped, Cmp, __gnu_pbds::rb_tree_tag,
__gnu_pbds::null_node_update>;
map() : base_type{} {}
template <typename... Args>
map(Args &&...args) : base_type(std::forward<Args>(args)...) {}
map(const map &other) : base_type(other) {}
map(map &&other) : base_type{} { this->swap(other); }
map &operator=(const map &other) = delete;
map &operator=(map &&other) = delete;
};
void update_all_keys_by(map &m, int offset) {
const_cast<Key *>(&m.node_begin().m_p_nd->m_value.first)->key += offset;
const_cast<Key *>(&m.node_begin().m_p_nd->m_value.first)->lazy += offset;
}
void update_all_values_by(map &m, int offset) {
m.node_begin().m_p_nd->m_value.second.a += offset;
const_cast<Key *>(&m.node_begin().m_p_nd->m_value.first)->lazy_v += offset;
}
struct Edge {
int other;
int length;
};
Key nonkey{0};
std::vector<std::vector<Edge>> adj;
int best;
int n, k;
void canonicalise_node(map::node_iterator it, map::node_iterator end) {
propagate(*it.m_p_nd, it.m_p_nd->m_value.first.lazy,
it.m_p_nd->m_value.first.lazy_v);
const_cast<Key *>(&it.m_p_nd->m_value.first)->lazy = 0;
const_cast<Key *>(&it.m_p_nd->m_value.first)->lazy_v = 0;
if (it.get_l_child() != end) {
canonicalise_node(it.get_l_child(), end);
}
if (it.get_r_child() != end) {
canonicalise_node(it.get_r_child(), end);
}
}
void canonicalise(map &m) { canonicalise_node(m.node_begin(), m.node_end()); }
void merge_into(map &into, map &from) {
if (into.size() < from.size()) {
into.swap(from);
}
canonicalise(from);
for (auto it = from.begin(); it != from.end(); it++) {
auto it1 = into.find(k - it->first.key);
if (it1 != into.end()) {
best = std::min(best, it->second.a + it1->second.a);
}
}
for (auto it = from.begin(); it != from.end(); it++) {
auto it1 = into.find(it->first.key);
if (it1 != into.end()) {
it1->second.a = std::min(it1->second.a, it->second.a);
} else {
into.insert({it->first.key, it->second.a});
}
}
}
map dfs(int node, int parent) {
map result;
result.insert({0, 0});
for (Edge e : adj[node]) {
if (e.other == parent) continue;
map m = dfs(e.other, node);
update_all_keys_by(m, e.length);
update_all_values_by(m, 1);
merge_into(result, m);
}
return result;
}
int best_path(int N, int K, int H[][2], int L[]) {
adj.resize(N);
best = N;
n = N;
k = K;
for (int i = 0; i < N - 1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
dfs(0, -1);
if (best == N)
return -1;
else
return best;
}
