| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1314358 | nguthianmangcay | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+3;
const int inf = 1e9+7;
#define ll long long
#define fi first
#define se second
#define VOI void
map<ll,int>best[N];
int ans = inf;
int n,k;
vector<pair<int,ll>>adj[N];
VOI DFS(int u,int pre){
best[u][0] = 0;
for(pair<int,ll> tmp : adj[u]){
int v = tmp.fi;
ll weight = tmp.se;
if(v == pre)continue;
DFS(v,u);
if(best[v].size() > best[u].size())swap(best[v],best[u]);
for(auto [len,paths] : best[v]){
ll newlen = k - weight - len;
if(newlen < 0)continue;
if(best[u].find(newlen) != best[u].end()){
ans = min(ans,paths + 1 + best[u][newlen]);
}
}
for(auto [len,paths] : best[v]){
if(best[u].find(len + weight) == best[u].end())best[u][len+weight] = inf;
best[u][len + weight] = min(best[u][len + weight],paths + 1);
}
}
}
VOI jiangly(){
cin>>n>>k;
for(int i=1;i<n;i++){
int x,y;
ll w;
cin>>x>>y>>w;
x++;
y++;
adj[x].push_back({y,w});
adj[y].push_back({x,w});
}
DFS(1,-1);
if(ans == inf)ans = -1;
cout<<ans;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
// if(fopen("QUANSENSEI.inp","r")){
// freopen("O(0).inp","r",stdin);
// }
// if(fopen("input.txt","r")){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// }
jiangly();
// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}