| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1179294 | hoang1707 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
int res=INT_MAX;
int n,k;
void dfs(vector<vector<pair<int,int>>>&g,int u,int p,int d,int deep,map<int,int> memo[]){
memo[u][deep]=d;
// cout<<"deep="<<deep<<",d="<<d<<",u="<<u<<endl;
for(auto &co:g[u]) {
int v=co.first,w=co.second;
if (v==p) continue;
dfs(g,v,u,d+1,deep+w,memo);
if (memo[u].size()<memo[v].size()) swap(memo[u],memo[v]);
for (auto &p:memo[v]) {
int w=p.second;
int val=deep+k-w;
if (memo[u].find(val)!=memo[u].end()) res=min(res,memo[u][val]-d+1);
}
for(auto &p:memo[v]) {
int fi=p.first,se=p.second;
if (memo[u].find(fi)==memo[u].end()) memo[u][fi]=se;
else memo[u][fi]=min(memo[u][fi],se);
// cout<<"v="<<v<<",w="<<w<<",val="<<val<<endl;
}
}
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
vector<vector<pair<int,int>>> g(n);
vector<pair<int,int>> edges;
for (int i=1;i<n;i++) {
int u,v;cin>>u>>v;
edges.emplace_back(u,v);
}
int len[n-1];
for (int i=0;i<n-1;i++) cin>>len[i];
for (int i=0;i<n-1;i++) {
int u=edges[i].first,v=edges[i].second;
g[u].push_back({v,len[i]});
g[v].push_back({u,len[i]});
}
map<int,int> memo[n];
int root=-1;
for (int i=0;i<n;i++) if (g[i].size()<=1) {
root=i;
break;
}
dfs(g,root,root,0,0,memo);
if (res==INT_MAX) cout<<-1<<endl; else cout<<res<<endl;
}