| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1287927 | soumil69 | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int MX = 2e5+1;
map<int,int> col[MX];
vector<pair<int,int>> adj[MX];
int ans = 1e9, k, n;
int w[MX];
void insert(int idx,pair<int,int> val){
val.first += w[idx];
val.second += 1;
if(val.first == k){
ans = min(ans,val.second);
}
if(val.first <= k){
if(!col[idx].count(val.first)) col[idx][val.first] = val.second;
else col[idx][val.first] = min(val.second, col[idx][val.first]);
}
}
void init(int cur,int par){
for(pair<int,int>& nxt:adj[cur]){
if(nxt.first != par){
w[nxt.first] = nxt.second;
init(nxt.first,cur);
}
}
}
void dfs(int cur,int par){
if(cur != 1){
insert(cur,{0,0});
}
for(pair<int,int>& nxt:adj[cur]){
int nx = nxt.first;
if(nx == par) continue;
dfs(nx,cur);
if(col[cur].size() < col[nx].size()){
swap(col[cur],col[nx]);
}
for(auto cols:col[nx]){
int val = cols.first;
int rem = k+w[cur] - val;
if(col[cur].count(rem)){
ans = min(ans,col[cur][rem]+cols.second-1);
}
insert(cur,cols);
}
}
}
vector<int> edg[MX];
signed main(){
cin>>n>>k;
for(int i = 0;i<n-1;i++){
int u,v;cin>>u>>v;
u++,v++;
edg[i] = {u,v,0};
}
for(int i = 0;i<n-1;i++){
cin>>edg[i][2];
adj[edg[i][0]].push_back({edg[i][1],edg[i][2]});
adj[edg[i][1]].push_back({edg[i][0],edg[i][2]});
}
init(1,0);
w[1] = 0;
dfs(1,0);
if(ans == 1e9) ans = -1;
cout<<ans<<endl;
return 0;
}