| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1129264 | hippo123 | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int n, k;
#define pr pair<int, int>
#define f first
#define s second
#define ll long long
#define pb push_back
const int ndim=1e5+10;
vector<vector<pr>> adj(ndim);
vector<bool> vis(ndim);
vector<int> d(ndim);
vector<int> in(ndim), out(ndim);
vector<int> col(ndim);
vector<int> par(ndim);
map<int, int> ms[ndim];
int ans=1e9;
void dfs(int nd, int par0){
if(vis[nd]) return;
vis[nd]=true;
par[nd]=par0;
//cout<<" nd= "<<nd<<endl;
ms[nd][0]=1; // start from itself
for (auto elem: adj[nd]){
if(!vis[elem.f]){
dfs(elem.f, nd);
// before combining, we can search
for (auto e: ms[elem.f]) {
if(e.f<k){
if(ms[nd].find(k-e.f)!=ms[nd].end()){
ans=min(ans, ms[nd][k-e.f]);
}
}
}
// combine it into it
for (auto e: ms[elem.f]) {
if(ms[nd].find(e.f+elem.s)!=ms[nd].end()){
ms[nd][e.f+elem.s]=min(ms[nd][e.f+elem.s], e.s+1); // increase node by 1
}
else ms[nd][e.f+elem.s]=e.s+1;
}
}
}
// search for single length
if(ms[nd].find(k)!=ms[nd].end()) ans=min(ans, ms[nd][k]);
}
int main(){
cin>>n>>k;
for (int i=0; i<n-1; i++) cin>>d[i];
for (int i=0; i<n-1; i++){
int a, b; cin>>a>>b;
adj[a].pb({b, d[i]}); adj[b].pb({a, d[i]});
}
dfs(0, 0);
if(ans==1e9) cout<<"-1";
else cout<<ans;
}