#include "race.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define ff(i,a,b) for(int i=a;i<=b;i++) #define fb(i,b,a) for(int i=b;i>=a;i--) using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<int,ll> pii; const int maxn = 200005; const int inf = 1e9 + 5; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // os.order_of_key(k) the number of elements in the os less than k // *os.find_by_order(k) print the k-th smallest number in os(0-based) int n; ll k; vector<pii> g[maxn]; ll rez = inf; map<ll,ll> dt[maxn]; void dfs(int v, int p, int duz, ll pw){ dt[v][pw] = duz; // cout << "v: " << v << endl; // cout << "duz: " << duz << endl; // cout << "pw: " << pw << endl; // cout << endl; for(auto c : g[v]){ int u = c.fi; ll w = c.se; if(u != p){ dfs(u, v, duz + 1, pw + w); int x = v, y = u; if(sz(dt[x]) < sz(dt[y]))swap(dt[x], dt[y]); for(auto c : dt[y]){ if(dt[x].count(k - c.fi + 2 * pw))rez = min(rez, dt[x][k - c.fi + 2 * pw] + c.se - 2 * duz); if(dt[x][c.fi] == 0)dt[x][c.fi] = c.se; else dt[x][c.fi] = min(dt[x][c.fi], c.se); } } } // cout << "v: " << v << endl; // for(auto c : dt[v])cout << c.fi << " " << c.se << endl; // cout << "-----------------------------" << endl; } int best_path(int N, int K, int H[][2], int L[]){ n = N; k = K; ff(i,1,n){ g[i].clear(); dt[i].clear(); } ff(i,0,n - 2){ int u = H[i][0] + 1; int v = H[i][1] + 1; ll w = L[i]; g[u].pb({v, w}); g[v].pb({u, w}); } dfs(1, -1, 1, 0); return (rez == inf ? -1 : rez); } //int main() //{ // ios::sync_with_stdio(false); // cout.tie(nullptr); // cin.tie(nullptr); // cin >> n >> k; // ff(i,1,n - 1){ // int u, v, w; // cin >> u >> v >> w; // g[u].pb({v, w}); // g[v].pb({u, w}); // } // dfs(1, -1, 1, 0); // cout << rez << endl; // return 0; //} /** 11 12 1 2 3 1 3 4 3 4 5 4 5 4 5 6 6 1 7 3 7 8 2 7 9 5 9 10 6 9 11 7 // probati bojenje sahovski ili slicno **/