#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 > > > anc[N] , arc[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]; bool is_rmv[N]; int up[19][N]; int dep[N]; void DFS(int v , int p) { if(v > 0) dep[v] = dep[p] + 1; up[0][v] = p; for(int i = 1;i < 19;i++) up[i][v] = up[i - 1][up[i - 1][v]]; for(pair < int , int > nxt : G[v]){ int u = nxt.first; if(u != p) DFS(u , 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; } void dfs(int v , int p , int centro , int nd , int wd) { anc[v].push_back({centro , {wd , nd}}); arc[centro].push_back({v , {wd , nd}}); for(pair < int , int > nxt : G[v]) { int u = nxt.first; if(u != p && !is_rmv[u]) dfs(u , v , centro , nd + 1 , wd + nxt.second); } } void build(int v) { int comp_sz = gsz(v , -1); int centro = find_centro(v , -1 , comp_sz); is_rmv[centro] = 1; dfs(centro , -1 , centro , 0 , 0); for(pair < int , int > nxt : G[centro]){ int u = nxt.first; if(!is_rmv[u]) build(u); } } int LCA(int u , int v) { if(dep[u] < dep[v]) swap(u , v); int dif = dep[u] - dep[v]; for(int i = 18;i >= 0;i--) { if((1 << i) & dif) u = up[i][u]; } if(u == v) return u; for(int i = 18;i >= 0;i--) { if(up[i][u] != up[i][v]) { u = up[i][u]; v = up[i][v]; } } return up[0][u]; } int dis(int u , int v) { int lca = LCA(u , v); return (dep[v] - dep[lca]) + (dep[u] - dep[lca]); } int get(int v , int k) { int ans = INF; for(pair < int , pair < int , int > > nxt1 : anc[v]) { int centro = nxt1.first; int wg = nxt1.second.first; int ng = nxt1.second.second; int need = k - wg; for(pair < int , pair < int , int > > nxt2 : arc[centro]) { int node = nxt2.first; int wgg = nxt2.second.first; int ngg = nxt2.second.second; if(wgg != need) continue; if(dis(v , centro) + dis(centro , node) != dis(v , node)) continue; ans = min(ans , ng + ngg); } } 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]); DFS(0 , -1); build(0); int ans = INF; for(int i = 0;i < N;i++) ans = min(ans , get(i , K)); if(ans == INF) ans = -1; return ans; }