#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <utility> 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 = 0; 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; } vector<int> solve(int p){ int mid = get_mid(p); kill[mid] = 1; vector<int> v(k+1,1e9); v[0] = 0; for (int i=0; i<graph[mid].size(); i++) { if(kill[graph[mid][i].second]) continue; vector<int> u = solve(graph[mid][i].second); int l = graph[mid][i].first; for (int j=0; j<=k - l; j++) { ret = min(ret,v[k-j-l] + u[j] + 1); } for (int j=0; j<=k - l; j++) { v[j+l] = min(v[j+l],u[j] + 1); } } return v; } 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])); } k = K; solve(0); return ret; } int main(){ int n,k; scanf("%d %d",&n,&k); int h[200005][2], l[200005]; for (int i=0; i<n-1; i++) { scanf("%d %d %d",&h[i][0],&h[i][1],&l[i]); } printf("%d",best_path(n,k,h,l)); }

race.cpp: In function 'int dfs(int, int)':
race.cpp:23: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:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<new_vis.size(); i++) {
                   ~^~~~~~~~~~~~~~~
race.cpp: In function 'std::vector<int> solve(int)':
race.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<graph[mid].size(); i++) {
                   ~^~~~~~~~~~~~~~~~~~
race.cpp: In function 'int main()':
race.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~
race.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&h[i][0],&h[i][1],&l[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccJ8OEAP.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccUuMngx.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status