#include "race.h" #include "bits/stdc++.h" using namespace std; const int N = 200001; const int INF = 1e9; int n; vector < pair < int , int > > G[N]; vector < pair < int , pair<int,int> > > dis[N]; void add_edge(int u,int v,int w){ G[u].push_back({v , w}); G[v].push_back({u , w}); } int sub[N] , par[N] , timer = 0; bool is_rmv[N]; int tin[N] , tout[N]; void DFS(int v , int p) { par[v] = p; tin[v] = ++timer; for(pair < int , int > nxt : G[v]) { int u = nxt.first; if(u == p) continue; DFS(u , v); } tout[v] = timer; } bool is_anc(int u , int v) { return (tin[v] >= tin[u] && tout[u] >= tout[v]); } int gsz(int v , int p){ sub[v] = 1; for(pair < int , int > nxt : G[v]){ int u = nxt.first; if(u == p or is_rmv[u]) continue; sub[v] += gsz(u , v); } return sub[v]; } int find_centro(int v , int p , int need){ for(pair < int , int > nxt : G[v]) { int u = nxt.first; if(u == p or is_rmv[u] or sub[u] <= need / 2) continue; return find_centro(u , v , need); } return v; } map < pair < int , pair < int , int > > , int > mp; map < pair < int , pair < int , int > > , int > can; void dfs(int v , int p , int imp , int nd , int wd , int centro) { dis[v].push_back({centro , {nd,wd}}); if(!can[{centro , {imp , wd}}]) { can[{centro , {imp , wd}}] = 1; mp[{centro , {imp , wd}}] = INF; } mp[{centro , {imp , wd}}] = min(mp[{centro , {imp , wd}}] , nd); for(pair < int , int > nxt : G[v]) { int u = nxt.first; if(u != p && !is_rmv[u]) dfs(u , v , imp , nd + 1 , wd + nxt.second , centro); } } void DFS(int centro) { dis[centro].push_back({centro , {0,0}}); for(pair < int , int > nxt : G[centro]) { int u = nxt.first; int w = nxt.second; if(!is_rmv[u]) dfs(u , centro , u , 1 , w , centro); } } void build(int v) { int comp_sz = gsz(v , -1); int centro = find_centro(v , -1 , comp_sz); DFS(centro); is_rmv[centro] = 1; for(pair < int , int > nxt : G[centro]){ int u = nxt.first; if(!is_rmv[u]) build(u); } } int get(int v , int k) { int ans = INF; for(pair < int , pair<int,int> > nxt : dis[v]) { int centro = nxt.first; int dist = nxt.second.first; int wdist = nxt.second.second; int node = -1; int need = k - wdist; for(pair < int , int > U : G[centro]) { if(U.first == par[centro]) continue; int u = U.first; if(is_anc(u , v)) node = u; } if(node == -1) node = par[centro]; for(pair < int , int > U : G[centro]) { if(U.first == node) continue; if(can[{centro , {U.first , need}}]) ans = min(ans , dist + mp[{centro , {U.first , need}}]); } } return ans; } int best_path(int N , int K , int H[][2] , int L[]) { n = N; for(int i = 0;i < N - 1;i++) add_edge(H[i][0] , H[i][1] , L[i]); build(0); DFS(0 , -1); int ans = INF; for(int i = 0;i < N;i++) ans = min(ans , get(i , K)); if(ans == INF) ans = -1; return ans; }