#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <vector> #include <utility> #include <queue> using namespace std; typedef pair<int,int> pi; vector<pi> graph[200005]; int ret = 1e9; int size[200005], maxtree[200005]; int kill[200005]; int k; vector<int> new_vis; int dfs(int p, int pa){ if(kill[p]) return 0; new_vis.push_back(p); int cs = 1; int maxv = 0; for (int i=0; i<graph[p].size(); i++) { if(graph[p][i].second == pa) continue; int t = dfs(graph[p][i].second,p); maxv = max(t,maxv); cs += t; } maxtree[p] = maxv; return size[p] = cs; } int get_mid(int p){ new_vis.clear(); memset(size,0,sizeof(size)); memset(maxtree,0,sizeof(maxtree)); int full = dfs(p,-1); int mid_pos = 0, mid_res =1e9; for (int i=0; i<new_vis.size(); i++) { maxtree[new_vis[i]] = max(maxtree[new_vis[i]],full - size[new_vis[i]]); if(mid_res > maxtree[new_vis[i]]){ mid_pos = new_vis[i]; mid_res = maxtree[mid_pos]; } } return mid_pos; } int *v; void solve(int p){ int mid = get_mid(p); kill[mid] = 1; memset(v,63,sizeof(v)); v[0] = 0; for (int i=0; i<graph[mid].size(); i++) { if(kill[graph[mid][i].second]) continue; queue<int> q,d,p,l; vector<int> cd1, cd2; if(graph[mid][i].first > k) continue; q.push(graph[mid][i].second); d.push(graph[mid][i].first); l.push(1); p.push(mid); while (!q.empty()) { int qf = q.front(); int df = d.front(); int pf = p.front(); int lf = l.front(); cd1.push_back(df); cd2.push_back(lf); ret = min(v[k-df] + lf,ret); q.pop(); d.pop(); p.pop(); l.pop(); for (int i=0; i<graph[qf].size(); i++) { int pos = graph[qf][i].second; if(kill[pos] || pos == pf) continue; if(df + graph[qf][i].first > k) continue; q.push(pos); d.push(df + graph[qf][i].first); p.push(qf); l.push(lf + 1); } } for (int i=0; i<cd1.size(); i++) { v[cd1[i]] = min(v[cd1[i]],cd2[i]); } } for (int i=0; i<graph[mid].size(); i++) { if(kill[graph[mid][i].second]) continue; solve(graph[mid][i].second); } } int best_path(int N, int K, int H[][2], int L[]){ for (int i=0; i<N-1; i++) { graph[H[i][0]].push_back(pi(L[i],H[i][1])); graph[H[i][1]].push_back(pi(L[i],H[i][0])); } v = (int* )calloc(K+1,sizeof(int)); k = K; solve(0); if(ret > 1e8) return -1; return ret; }

race.cpp: In function 'int dfs(int, int)':
race.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<graph[p].size(); i++) {
                   ~^~~~~~~~~~~~~~~~
race.cpp: In function 'int get_mid(int)':
race.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<new_vis.size(); i++) {
                   ~^~~~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:56:23: warning: argument to 'sizeof' in 'void* memset(void*, int, size_t)' call is the same expression as the destination; did you mean to dereference it? [-Wsizeof-pointer-memaccess]
     memset(v,63,sizeof(v));
                       ^
race.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<graph[mid].size(); i++) {
                   ~^~~~~~~~~~~~~~~~~~
race.cpp:79:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i=0; i<graph[qf].size(); i++) {
                           ~^~~~~~~~~~~~~~~~~
race.cpp:89:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<cd1.size(); i++) {
                       ~^~~~~~~~~~~
race.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<graph[mid].size(); i++) {
                   ~^~~~~~~~~~~~~~~~~~