| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1281031 | trinm01 | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>
const ll mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const ll oo = 1e18 + 7;
const int base = 10;
int n, k;
vector<pii> adj[MAXN];
int del[MAXN], sz[MAXN];
void count(int u, int p){
sz[u]=1;
for(auto [v, w]:adj[u]){
if(v==p || del[v]) continue;
count(v, u);
sz[u]+=sz[v];
}
}
int find(int u, int p, int m){
for(auto [v, w]:adj[u]){
if(v==p || del[v]) continue;
if(sz[v]>m/2){
return find(v, u, m);
}
}
return u;
}
int ans=oo;
int d[MAXN], h[MAXN];
int mp[1000005];
void reset(int u, int p){
if(d[u]<=1e6){
mp[d[u]]=oo;
}
if(k-d[u]>=0){
mp[k-d[u]]=oo;
}
for(auto [v, w]:adj[u]){
if(v==p || del[v]) continue;
h[v]=h[u]+1;
d[v]=d[u]+w;
reset(v, u);
}
}
void dfs1(int u, int p){
if(k-d[u]>=0){
ans=min(ans, h[u]+mp[k-d[u]]);
}
for(auto [v, w]:adj[u]){
if(v==p || del[v]) continue;
h[v]=h[u]+1;
d[v]=d[u]+w;
dfs1(v, u);
}
}
void dfs2(int u, int p){
if(d[u]<=1e6)
mp[d[u]]=min(mp[d[u]], h[u]);
for(auto [v, w]:adj[u]){
if(v==p || del[v]) continue;
dfs2(v, u);
}
}
void solve(int u){
h[u]=d[u]=0;
reset(u, 0);
mp[0]=0;
for(auto [v, w]:adj[u]){
if(del[v]) continue;
h[v]=h[u]+1;
d[v]=d[u]+w;
dfs1(v, u);
dfs2(v, u);
}
reset(u, 0);
mp[0]=0;
FOD(i, (int)adj[u].size()-1, 0){
auto [v, w]=adj[u][i];
if(del[v]) continue;
h[v]=h[u]+1;
d[v]=d[u]+w;
dfs1(v, u);
dfs2(v, u);
}
}
void centroid(int u, int p){
count(u, 0);
int root=find(u, 0, sz[u]);
solve(root);
del[root]=1;
for(auto [v, w]:adj[root]){
if(del[v]) continue;
centroid(v, root);
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("test.txt", "r", stdin);
// freopen("o2.out", "w", stdout);
if(fopen(".inp", "r")){
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
cin >> n >> k;
FOR(i, 1, n-1){
int u, v, c;
cin >> u >> v >> c;
u++;
v++;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
centroid(1, 0);
if(ans==oo) ans=-1;
cout << ans;
return 0;
}