| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1177538 | LmaoLmao | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using aa = array<int,3>;
const int N = 1e6+1;
const int INF = 1e9;
int s[200005];
bool del[200005];
vector<ii> adj[200005];
int mp[1000005];
int d,k,ans;
int dfs(int u,int p) {
s[u]=1;
for(ii v:adj[u]) {
if(del[v.fi] || v.fi==p) continue;
s[u]+=dfs(v.fi,u);
}
return s[u];
}
int citron(int u,int p,int sz) {
for(ii v:adj[u]) {
if(del[v.fi] || v.fi==p) continue;
if(s[v.fi]*2>sz) return citron(v.fi,u,sz);
}
return u;
}
void get(int u,int p,int cur,int len,int type) {
d=max(d,cur);
if(len>k) return;
if(type) {
ans=min(ans,cur+mp[k-len]);
}
else {
mp[len]=min(mp[len],cur);
}
//if(u==1 && cur==1) cout << mp[1];
for(ii v:adj[u]) {
if(v.fi!=p && !del[v.fi]) get(v.fi,u,cur+1,len+v.se,type);
}
}
void build(int u) {
int ctr=citron(u,0,dfs(u,0));
d=0;
del[ctr]=1;
for(ii v:adj[ctr]) {
if(!del[v.fi]) {
get(v.fi,0,1,v.se,1);
get(v.fi,0,1,v.se,0);
//if(ctr==2) cout << k << ' ' << v << endl;
}
}
//cout << ans << ' ' << d << endl;
for(int i=1;i<=d;i++) {
mp[i]=1e9;
}
for(ii v:adj[ctr]) {
if(del[v.fi]) continue;
build(v.fi);
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n >> k;
for(int i=1;i<n;i++) {
int u,v,w;
cin >> u >> v >> w;
++v;
++u;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
for(int i=1;i<=k;i++) {
mp[i]=1e9;
}
mp[0]=0;
ans=1e9;
build(1);
if(ans!=1e9) cout << ans; else cout << -1;
return 0;
}