#include <bits/stdc++.h>
using namespace std;
#define MAX_N 300000
long long n,k,val=0;
long long ans=1e7;
long long cnst1[MAX_N],cnst2[MAX_N];
vector <array<long long,2>> v[MAX_N];
set <array<long long,2>> nodes[MAX_N];
void dfs(long long i,long long last){
if(v[i].size()==1&&i!=1){
nodes[i].insert({0,0});
return;
}
long long x,siz=0,c;
for(auto [j,w]:v[i]){
if(j==last) continue;
dfs(j,i);
if(nodes[j].size()>siz){
siz=nodes[j].size();
x=j;
c=w;
}
}
swap(nodes[i],nodes[x]);
nodes[i].insert({0-cnst1[x],0-cnst2[x]});
long long co=c,le=1;
auto it=nodes[i].lower_bound({(long long)k-cnst1[x]-co,-10000000ll});
if(it!=nodes[i].end()&&(*it)[0]==(long long)k-cnst1[x]-co){
ans=min(ans,le+(*it)[1]+cnst2[x]);
}
cnst1[i]=cnst1[x]+c,cnst2[i]=cnst2[x]+1;
nodes[i].insert({co-cnst1[i],le-cnst2[i]});
for(auto [j,w]:v[i]){
if(j==last||j==x) continue;
co=w,le=1;
auto it=nodes[i].lower_bound({(long long)k-cnst1[i]-co,-10000000ll});
if(it!=nodes[i].end()&&(*it)[0]==(long long)k-cnst1[i]-co){
ans=min(ans,le+(*it)[1]+cnst2[i]);
}
nodes[i].insert({co-cnst1[i],le-cnst2[i]});
for(auto [cost,len]:nodes[j]){
co=cost+cnst1[j]+w,le=len+cnst2[j]+1;
it=nodes[i].lower_bound({(long long)k-cnst1[i]-co,-10000000ll});
if(it!=nodes[i].end()&&(*it)[0]==(long long)k-cnst1[i]-co){
ans=min(ans,le+(*it)[1]+cnst2[i]);
}
}
for(auto [cost,len]:nodes[j]){
co=cost+cnst1[j]+w,le=len+cnst2[j]+1;
nodes[i].insert({co-cnst1[i],le-cnst2[i]});
}
nodes[j].clear();
}
return;
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;
k=K;
for(int i=0;i<n-1;i++){
v[H[i][0]+1].push_back({H[i][1]+1,L[i]});
v[H[i][1]+1].push_back({H[i][0]+1,L[i]});
if(L[i]==k) return 1;
}
dfs(1,0);
if(ans!=1e7) return (int)ans;
else return -1;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, K;
int H[MAX_N][2];
int L[MAX_N];
int solution;
cin>>N>>K;
for(int i=0;i<N-1;i++) cin>>H[i][0]>>H[i][1]>>L[i];
cout<<best_path(N,K,H,L)<<endl;
return 0;
}
Compilation message
race.cpp: In function 'void dfs(long long int, long long int)':
race.cpp:15:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
15 | for(auto [j,w]:v[i]){
| ^
race.cpp:18:27: warning: comparison of integer expressions of different signedness: 'std::set<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
18 | if(nodes[j].size()>siz){
| ~~~~~~~~~~~~~~~^~~~
race.cpp:33:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
33 | for(auto [j,w]:v[i]){
| ^
race.cpp:43:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
43 | for(auto [cost,len]:nodes[j]){
| ^
race.cpp:50:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
50 | for(auto [cost,len]:nodes[j]){
| ^
race.cpp: In function 'int main()':
race.cpp:79:9: warning: unused variable 'solution' [-Wunused-variable]
79 | int solution;
| ^~~~~~~~
race.cpp: In function 'void dfs(long long int, long long int)':
race.cpp:27:56: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
27 | auto it=nodes[i].lower_bound({(long long)k-cnst1[x]-co,-10000000ll});
| ~~~~~~~~~~~~~~~~~~~~~^~~
race.cpp:14:15: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
14 | long long x,siz=0,c;
| ^
/usr/bin/ld: /tmp/ccoqlB1Y.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc6oglqX.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
