| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1310441 | khangai11 | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
vector<vector<pair<ll,ll>>> g;
vector<ll> child;
vector<char> rm;
ll dfs(ll i,ll p){
child[i]=1;
for(auto x:g[i]){
ll z=x.first;
if(z!=p and rm[z]==0)
child[i]+=dfs(z,i);
}
return child[i];
}
ll center(ll i,ll p,ll ts){
ll n=ts/2;
for(auto x:g[i]){
ll z=x.first;
if(z==p or rm[z]==1){
continue;
}
if(child[z]>n){
return center(z,i,ts);
}
}
return i;
}
map<ll,ll> mp;
ll k,D=1e9;
void dfs1(ll i,ll p,map<ll,ll> &mp1,ll d,ll de){
if(d>k){
return;
}
if(mp1.find(d)==mp1.end()){
mp1[d]=de;
}else{
mp1[d]=min(mp1[d],de);
}
if(mp.find(k-d)!=mp.end()){
D=min(D,mp[k-d]+de);
}
for(auto z:g[i]){
if(p==z.first or rm[z.first]==1){
continue;
}
dfs1(z.first,i,mp1,d+z.second,de+1);
}
}
void build(ll i){
dfs(i,-1);
ll c=center(i,-1,child[i]);
rm[c]=1;
for(auto z:g[c]){
if(rm[z.first]==1){
continue;
}
map<ll,ll> mp1;
dfs1(z.first,c,mp1,z.second,1);
for(auto x:mp1){
if(mp.find(x.first)==mp.end()){
mp[x.first]=x.second;
}else{
mp[x.first]=min(mp[x.first],x.second);
}
}
}
for(auto z:g[c]){
if(rm[z.first]==0)
build(z.first);
}
}
void solve(){
ll n;
cin>>n>>k;
g.resize(n);
rm.resize(n,0);
child.resize(n);
for(ll a=0;a<n-1;a++){
ll u,v,x;
cin>>u>>v>>x;
g[u].push_back({v,x});
g[v].push_back({u,x});
}
build(0);
if(D==1e9){
cout<<-1<<endl;
}else
cout<<D<<endl;
}
signed main(){
ios::sync_with_stdio();
cin.tie(0);
cout.tie(0);
// freopen("yinyang.in", "r", stdin);
// freopen("yinyang.out", "w", stdout);
ll t=1;
// cin>>t;
for(ll a=0;a<t;a++){
solve();
}
}