#include "race.h" #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; const int oo = 1e9; int n, k; vector<array<int, 2>> adj[N]; struct CentroidDecomposition { vector<int> sub; vector<bool> removed; vector<int> mn; void init(int n) { sub.assign(n + 1, 0); mn.assign(k + 1, oo); removed.assign(n + 1, false); } int getsub(int u, int p) { sub[u] = 1; for (auto &[v, w] : adj[u]) { if (v != p && !removed[v]) sub[u] += getsub(v, u); } return sub[u]; } int find(int u, int p, int half) { for (auto &[v, w] : adj[u]) { if (v != p && !removed[v] && sub[v] > half) return find(v, u, half); } return u; } void getdist(int u, int p, int d, int we, vector<array<int, 2>> &dist) { dist.push_back({d, we}); for (auto &[v, w] : adj[u]) { if (v != p && !removed[v]) getdist(v, u, d + 1, we + w, dist); } } int solveK(int centroid, int treesize) { int res = oo; for (auto &[v, w] : adj[centroid]) { if (removed[v]) continue; vector<array<int, 2>> dist; getdist(v, centroid, 1, w, dist); for (auto &[d, w] : dist) { if (w > k) { continue; } res = min(res, mn[k - w] + 1); } for (auto &[d, w] : dist) { if (w <= k) mn[w] = min(mn[w], d); } } fill(mn.begin(), mn.begin() + (treesize >> 1) + 1, oo); return res; } int solve(int u) { int centroid = find(u, -1, getsub(u, -1) >> 1); int res = solveK(centroid, sub[u]); removed[centroid] = true; for (auto &[v, w] : adj[centroid]) { if (!removed[v]) res = min(res, solve(v)); } return res; } }; int best_path(int N, int K, int H[][2], int L[]) { n = N, k = K; for (int i = 0; i < n - 1; ++i) { int u = H[i][0], v = H[i][1]; ++u, ++v; adj[u].push_back({v, L[i]}); adj[v].push_back({u, L[i]}); } CentroidDecomposition cd; cd.init(n + 5); int res = cd.solve(1); return (res == oo ? -1 : res); } /* @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@}()))(([]}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{]()<>>>^><>>><>><<<<(#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@{})<<>**+++**+*^++*^^^^^^<<)#@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@%(^*>+++====~~~+=~~+==*=+*+*<^^[@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@#<**+^==+*~~----=+---=~-~~~~~==>**<}@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@{([*^==~~==-----:-=---:-:------~~>*++}@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@<^<=~~-~~-:::::::~:::::::::---=~=+=^^{@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@%>))^=~---::::::.:.::.:..-::::::-~~^=+)){@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@##))^~~~-~+::::.......:..:.-:::-:=~+<+>]{%@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@%(()*=*~*=^:~:-.::.::.:....~::::-=~+)<^(%@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@}}()>+***<^-^-~:~::*-.~::::=----=*=^>))]{@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@%@]])<<^)*])~<~=:++-)+-^---:*~--~+><>)))[%@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@%[{()]<])%<=<+>-><=)>~)=~=~^==~=*<<)<(){@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@%@@]([){[]})(*)+)]*]]=]]=++^*+~^)(<)[(]#@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@}{(<<<>)]}>()]}]{[<))^*)>^**<})([]<}%@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@<>^^^^)]<*()[]]<>>)<^]<<<>(]>(}[}@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@<>^^^([>>^^^^^>^^^^>>>)()<<>]]]@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@[>^>[[)>^^^^^^^^^^^^^><<]<>><]@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@#>>^]]>^^^^^^^^^^^^^^>^^(>{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@(>>>({[}[^^^^^^^^^^^^^^>[%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@(>><>>^^^^^^^^^^^^^^^>){%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@%<>]><>^^^^^^^^^^^^><]}}}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@{<><])<><<^^^^^>)[}}{[[}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@{[>>^^^^^^^^>)[{}}}}}[}{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@%}[>>^^^^>){}}}}}}}}}}[}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@{}}#{}[}}}}}}}}}}}}}()%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@%@@@@@@@@@@@@@@}}}}{}}}}}}}}}}}}}]>>(%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{}}}{}}}}}}}}}}}})>>>]}{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@%{{}}}}}}}}}}}}]<]<>>>>>[}%@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@{}}}}}}{[[}}}[)>>))>>>>>><[%@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@{}}}}}}}}))(>>>>>[>>>>>>>><{@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@{}}}})>>[{<>>>^^()<<>>>>>><}@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@{)<<>><[}>>>>>[<](>>><<}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{]<<(]>><}])[{#%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ */