#include "race.h" #include <bits/stdc++.h> using namespace std; #define MOD1 1000000007 #define MOD2 998244353 #define fir first #define sec second #define pushf push_front #define pushb push_back #define popf pop_front #define popb pop_back #define mp make_pair #define all(a) a.begin(), a.end() #define lbound(v, x) lower_bound(all(v), x) - v.begin() #define ubound(v, x) upper_bound(all(v), x) - v.begin() #define chmax(a, b) a = max(a, b) #define chmin(a, b) a = min(a, b); #define FOR1(a) for (int _ = 0; _ < (a); ++_) #define FOR2(i, a) for (int i = 0; i < (a); ++i) #define FOR3(i, a, b) for (int i = (a); i < (b); ++i) #define RFOR1(a) for (int _ = (a)-1; _ >= 0; --_) #define RFOR2(i, a) for (int i = (a)-1; i >= 0; --i) #define RFOR3(i, a, b) for (int i = (b)-1; i >= (a); --i) #define overload3(a, b, c, d, ...) d // Always choose the fourth argument to call. Hence, which function to call is determined by the number of given arguments. #define REP(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__) #define RREP(...) overload3(__VA_ARGS__, RFOR3, RFOR2, RFOR1)(__VA_ARGS__) typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<bool> vb; typedef vector<char> vc; typedef vector<string> vs; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vi> vvi; typedef vector<vll> vvll; typedef vector<vb> vvb; typedef vector<vc> vvc; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; typedef queue<int> qi; typedef queue<ll> qll; typedef queue<pii> qpii; typedef queue<pll> qpll; typedef deque<int> dqi; typedef deque<ll> dqll; typedef deque<pii> dqpii; typedef deque<pll> dqpll; typedef priority_queue<int> pqi; typedef priority_queue<ll> pqll; typedef priority_queue<pii> pqpii; typedef priority_queue<pll> pqpll; typedef priority_queue<int, vi, greater<int> > r_pqi; typedef priority_queue<ll, vll, greater<ll> > r_pqll; typedef priority_queue<pii, vpii, greater<pii> > r_pqpii; typedef priority_queue<pll, vpll, greater<pll> > r_pqpll; const int INF = 1e8; const int maxn = 2e5+5; int k, mx; int ans = INF; vpii adj[maxn]; int sub_size[maxn]; int len[maxn]; bool removed[maxn]; int get_sub_size(int u, int par = 0) { sub_size[u] = 1; for (auto [v, w] : adj[u]) { if (v == par || removed[v]) { continue; } sub_size[u] += get_sub_size(v, u); } return sub_size[u]; } int get_centr(int u, int tree_size, int par = 0) { for (auto [v, w] : adj[u]) { if (v == par || removed[v]) { continue; } if (sub_size[v] * 2 > tree_size) { return get_centr(v, tree_size, u); } } return u; } void get_dists(int u, bool fil, int par, int depth, int cnt = 1) { if(depth > k) { return; } if(fil) { chmin(len[depth], cnt); } else { chmin(ans, cnt + len[k - depth]); } chmax(mx, depth); for (auto [v, w] : adj[u]) { if (v == par || removed[v]) { continue; } get_dists(v, fil, u, depth + w, cnt + 1); } return; } // build centr tree void build(int u) { int centr = get_centr(u, get_sub_size(u)); /* * For all nodes in the subtree rooted at `centr`, calculate their * distances to the centr */ mx = 0; removed[centr] = true; len[0] = 1; for (auto [v, w] : adj[centr]) { if (removed[v]) { continue; } get_dists(v, 0, centr, w); get_dists(v, 1, centr, w); } fill(len+1, len + mx + 1, INF); for (auto [v, w] : adj[centr]) { if (removed[v]) { continue; } build(v); } } int best_path(int n, int K, int H[][2], int L[]) { k = K; REP(i, n-1) { int a = H[i][0], b = H[i][1], c = L[i]; adj[a].pushb(mp(b, c)); adj[b].pushb(mp(a, c)); } memset(removed, 0, sizeof(removed)); fill(len, len + n, INF); build(0); if(ans >= INF) { ans = -1; } return ans; }