//region template
#ifdef IS_DEBUG
#pragma ide diagnostic ignored "hicpp-signed-bitwise"
#pragma ide diagnostic ignored "cert-err58-cpp"
#pragma ide diagnostic ignored "cppcoreguidelines-pro-type-member-init"
#pragma ide diagnostic ignored "bugprone-reserved-identifier"
#endif
#include <bits/stdc++.h>
#include <bits/extc++.h>
#ifndef IS_DEBUG
#define dout false && cout
#endif
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define memset0(x,i) memset(x,i,sizeof(x))
#define count1 __builtin_popcount
#define lead0 __builtin_clz
#define trail0 __builtin_ctz
#define min(...) _min(__VA_ARGS__)
#define max(...) _max(__VA_ARGS__)
#define FOR(i,l,r) for(int i=l;i<r;++i)
#define FORe(i,l,r) for(int i=l;i<=r;++i)
#define ROF(i,l,r) for(int i=r-1;i>=l;--i)
#define ROFe(i,l,r) for(int i=r;i>=l;--i)
#define trav(a,v) for(auto&a:v)
using ll = long long;
using vi = vector<int>;
using pii = pair<int,int>;
using db = double;
using ld = long double;
template<size_t x>struct lg2{enum{v=1+lg2<(x>>1)>::v};};template<>struct lg2<0>{enum{v=0};};
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline ll cdiv(ll a,ll b){return a/b+((a^b)>0&&a%b);}
inline ll fdiv(ll a,ll b){return a/b-((a^b)<0&&a%b);}
bool prime(int n){if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i+=6)if(n%i==0||n%(i+2)==0)return false;return true;}
template<class T>using set2 = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T1,class T2>using map2 = tree<T1,T2,less<T1>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>using heap = __gnu_pbds::priority_queue<T,greater<T>,pairing_heap_tag>;
template<class T>using max_heap = __gnu_pbds::priority_queue<T,less<T>,pairing_heap_tag>;
template<class T1,class T2>using unordered_map2 = gp_hash_table<T1,T2>;
template<class T1,class T2>unordered_map2<T1,T2> unordered_map2_size(int exp2){
return unordered_map2<T1,T2>({},{},{},{},{(uint32_t)1<<exp2});}
template<class T>using unordered_set2 = unordered_map2<T,null_type>;
template<class T>unordered_set2<T> unordered_set2_size(int exp2) {return unordered_map2_size<T,null_type>(exp2);}
template<class T>constexpr const T&_min(const T&x,const T&y){return x<y?x:y;}
template<class T>constexpr const T&_max(const T&x,const T&y){return x<y?y:x;}
template<class T,class...Ts>constexpr const T&_min(const T&x,const Ts&...xs){return _min(x,_min(xs...));}
template<class T,class...Ts>constexpr const T&_max(const T&x,const Ts&...xs){return _max(x,_max(xs...));}
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);
template<class T> void re(T& x) { cin >> x; }
void re(db& d) { string t; re(t); d = stod(t); }
void re(ld& d) { string t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.fi,p.se); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
template<class A> void pr(A x) { cout << x; }
template<class H, class... T> void pr(const H& h, const T&... t) { pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
void setIO(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#ifdef IS_DEBUG
freopen("../input.txt", "r", stdin);
#endif
}
namespace std{template<class T1,class T2> struct hash<pair<T1,T2>>{
size_t operator()(const pair<T1,T2>&p)const{return 31*hash<T1>{}(p.fi)+hash<T2>{}(p.se);}
};}
template<class T>struct BIT{
T n,*a;
T sum(int i){T s=0;for(i++;i>0;i-=i&-i)s+=a[i];return s;}
void edit(int i,T x){for(i++;i<=n;i+=i&-i)a[i]+=x;}
void init(int m){n=m;a=new T[n+1]();}
void init(T*arr,int m){init(m);FOR(i,0,n)edit(i,arr[i]);}
BIT()=default;BIT(T*arr,int m){init(arr,m);}~BIT(){delete[]a;}
};
//endregion
struct T {
unordered_map2<int, int> t;
int k1 = 0;
int k2 = 0;
int size() {
return t.size();
}
int get(int a) {
auto it = t.find(a - k1);
if (it != t.end()) {
return it->se + k2;
}
else {
return -1;
}
}
void insert(int a, int b) {
auto it = t.find(a - k1);
if (it != t.end()) {
it->se = min(it->se, b - k2);
}
else {
t[a - k1] = b - k2;
}
}
void swap(T &other) {
std::swap(k2, other.k2);
std::swap(k1, other.k1);
t.swap(other.t);
}
};
const int MaxN = 200001;
int N, K;
vector<pii> adj[MaxN];
int best = INT_MAX;
T dfs(int a, int p) {
T t;
t.insert(0, 0);
trav(e, adj[a]) {
int b = e.fi;
int l = e.se;
if (b == p) continue;
T t1 = dfs(b, a);
t1.k1 += l;
t1.k2++;
if (t1.size() > t.size()) {
t.swap(t1);
}
trav(x, t1.t) {
int len = x.fi + t1.k1;
int score = x.se + t1.k2;
int result = t.get(K - len);
if (result != -1) {
best = min(best, result + score);
}
}
trav(x, t1.t) {
int len = x.fi + t1.k1;
int score = x.se + t1.k2;
if (len < K) {
t.insert(len, score);
}
}
}
return t;
}
int best_path(int _N, int _K, int H[][2], int L[]) {
N = _N;
K = _K;
FOR(i, 0, N-1) {
int a = H[i][0];
int b = H[i][1];
adj[a].eb(b, L[i]);
adj[b].eb(a, L[i]);
}
dfs(0, 0);
if (best == INT_MAX)
best = -1;
return best;
}
#ifdef IS_DEBUG
int main() {
setIO();
int n, k;
re(n, k);
int h[n][2], l[n];
FOR(i, 0, n-1) {
re(h[i][0], h[i][1], l[i]);
}
ps(best_path(n, k, h, l));
return 0;
}
#endif
Compilation message
/usr/lib/gcc/x86_64-linux-gnu/9/../../../x86_64-linux-gnu/crt1.o: In function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
