#include <bits/stdc++.h>
//#include <race.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
using namespace std;
const int MOD = 1e9+7, MAXN = 2e5+5;
const string NAME = "test";
int n,k,rs=MAXN,sz[MAXN];
bool del[MAXN];
vector<pair<int,int>> adj[MAXN];
void GetSize(int u, int par){
sz[u]=1;
for(pair<int,int> p : adj[u])
if(p.fi!=par&&!del[p.fi]) GetSize(p.fi,u), sz[u]+=sz[p.fi];
}
int Centroid(int u, int par){
for(pair<int,int> p : adj[u])
if(p.fi!=par&&!del[p.fi]&&sz[p.fi]>(n>>1)) return Centroid(p.fi,u);
return u;
}
void dfs(int u, int par, bool type, int cur, ll len, int cnt[]){
if(k<len) return;
if(type==1) cnt[len] = !cnt[len] ? cur : min(cnt[len],cur);
else if(type==0&&cnt[k-len]) rs=min(rs,cnt[k-len]+cur);
else if(len==k) rs=min(rs,cur);
for(pair<int,int> p : adj[u])
if(p.fi!=par) dfs(p.fi,u,type,cur+1,len+p.se,cnt);
}
void CentroidDecomposition(int u){
GetSize(u,0), n=sz[u];
int root=Centroid(u,0);
int cnt[k+5];
memset(cnt,0,sizeof(cnt));
for(pair<int,int> p : adj[root])
if(!del[p.fi]) dfs(p.fi,root,0,1,p.se,cnt), dfs(p.fi,root,1,1,p.se,cnt);
del[root]=1;
for(pair<int,int> p : adj[root])
if(!del[p.fi]) CentroidDecomposition(p.fi);
}
int best_path(int N, int K, int h[][2], int l[]){
n=N, k=K;
for(int i = 1; i<n; ++i)
adj[h[i-1][0]+1].pb(h[i-1][1]+1,l[i-1]), adj[h[i-1][1]+1].pb(h[i-1][0]+1,l[i-1]);
CentroidDecomposition(1);
return rs==MAXN ? -1 : rs;
}
int main()
{
tt;
if(fopen((NAME + ".INP").c_str(), "r")) fo;
cin >> n >> k;
int h[n][2], l[n];
for(int i = 0; i<n-1; ++i)
cin >> h[i][0] >> h[i][1] >> l[i];
cout << best_path(n,k,h,l);
cerr << 1.0L*clock()/CLOCKS_PER_SEC << "s\n";
}
Compilation message
race.cpp: In function 'int main()':
race.cpp:4:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
4 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:64:45: note: in expansion of macro 'fo'
64 | if(fopen((NAME + ".INP").c_str(), "r")) fo;
| ^~
race.cpp:4:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
4 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:64:45: note: in expansion of macro 'fo'
64 | if(fopen((NAME + ".INP").c_str(), "r")) fo;
| ^~
/usr/bin/ld: /tmp/ccbZaxio.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccsPXPLr.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
