#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
const int oo = 1e18;
#define quickly ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define print(a,l,r) for(int OK(l); OK <= r ; ++OK){ if(a[OK] < oo){cout << a[OK] <<' ';} else{cout << "- ";}} cout << '\n';
#define prints(a) for(auto i : a){ cout << i <<' ';} cout << '\n';
#define printz(a,l,r) for(int OK(1) ; OK <= l ; ++OK){for(int KO(1) ; KO <= r ; ++KO){if(a[OK][KO] < oo){cout << a[OK][KO] <<' ';}else{cout << "- ";}}cout << '\n';} cout << '\n';
#define fs first
#define sd second
#define ii pair<int, int>
#define iii pair<int, ii>
#define all(a) a.begin(), a.end()
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, k, mix = oo, ans(0);
int d = 0;
vector<ii> a[N];
struct Centroid{
int sz[N];
int high[N], len[N];
bool cen[N];
map<int, ii> mp;
void DFS(int u, int par){
sz[u] = 1;
for(ii e : a[u]){
int v = e.fs;
if(v == par || cen[v]){
continue;
}
DFS(v, u);
sz[u] += sz[v];
}
}
int find_centroid(int u, int par, int mx){
for(ii e : a[u]){
int v = e.fs;
if(v == par || cen[v]){
continue;
}
if(sz[v] > mx / 2){
return find_centroid(v, u, mx);
}
}
return u;
}
void DFS_ANS(int u, int par, bool check){
if(high[u] > k){
return;
}
if(check){
if(mp[k - high[u]].sd != 0){
if(mix > mp[k - high[u]].fs + len[u]){
mix = mp[k - high[u]].fs + len[u];
ans = 0;
d = mp[k - high[u]].sd;
}
else if(mix == mp[k - high[u]].fs + len[u]){
d += mp[k - high[u]].sd;
}
}
}
else{
ii &x = mp[high[u]];
if(x.fs > len[u] || x.sd == 0){
x.fs = len[u];
x.sd = 1;
}
else if(x.sd == len[u]){
x.sd++;
}
}
for(ii e : a[u]){
int v = e.fs, w= e.sd;
if(v == par || cen[v]){
continue;
}
len[v] = len[u] + 1;
high[v] = high[u] + w;
DFS_ANS(v, u, check);
}
}
void tree(int u){
// tim centroid
mp.clear();
DFS(u, -1);
int centroid = find_centroid(u, -1, sz[u]);
cen[centroid] = true;
d = 0;
mp[0].sd = 1;
high[centroid] = len[centroid] = 0;
// tim dap an
for(ii e : a[centroid]){
int v = e.fs, w = e.sd;
if(cen[v]){
continue;
}
high[v] = w;
len[v] = 1;
DFS_ANS(v, centroid, 1);
DFS_ANS(v, centroid, 0);
}
ans += d;
// Con con nho hon
for(ii e : a[centroid]){
int v = e.fs, w = e.sd;
if(cen[v]){
continue;
}
tree(v);
}
}
};
Centroid Cen;
signed main(){ quickly
cin >> n >> k;
for(int i(1) ; i < n ; ++i){
int u, v, c;
cin >> u >> v >> c;
a[u + 1].push_back({v + 1, c});
a[v + 1].push_back({u + 1, c});
}
Cen.tree(1);
if(ans == 0){
cout << -1;
return 0;
}
cout << ans * 2 << '\n';
}
Compilation message
race.cpp: In member function 'void Centroid::tree(long long int)':
race.cpp:125:33: warning: unused variable 'w' [-Wunused-variable]
125 | int v = e.fs, w = e.sd;
| ^
/usr/bin/ld: /tmp/ccShLMty.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccGcFiSy.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccGcFiSy.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status
