| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1147941 | Kodik | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ss second
#define ff first
typedef long long ll;
#define int ll
using pi = array<ll, 2>;
const int MOD = 1e9+7;
int n, k;
const int maxn = 2e5;
vector<pair<int,int>> g[maxn];
int sz[maxn];
pi node[maxn];
map<int,int> len_to_dep[maxn];
void dfs_sz(int v, int p, int d, int l){
sz[v] = 1;
node[v] = {l, d};
for(auto &[w,u] : g[v]){
if(u!=p){
dfs_sz(u, v, d+1, l+w);
sz[v] += sz[u];
}
}
}
int ans = 1e9;
void dfs(int v, int p){
int mx = -1, bigChild = -1;
for(auto& [w, u] : g[v]){
if(u!=p&&sz[u]>mx){
mx = sz[u];
bigChild = u;
}
if(u!=p){
dfs(u, v);
}
}
if(bigChild!=-1){
swap(len_to_dep[v], len_to_dep[bigChild]);
}
if(len_to_dep[v].count(node[v][0])>0) len_to_dep[v][node[v][0]] = min(len_to_dep[v][node[v][0]], node[v][1]);
else len_to_dep[v][node[v][0]] = node[v][1];
for(auto &[w, u] : g[v]){
if(u!=p&&u!=bigChild){
for(auto &[l, d] : len_to_dep[u]){
int seek = k-l+node[v][0];
if(len_to_dep[v].count(seek)>0){
ans = min(ans, d+len_to_dep[v][seek]-2*node[v][1]);
}
}
for(auto &[l, d] : len_to_dep[u]){
if(len_to_dep[v].count(l)>0) len_to_dep[v][l] = min(len_to_dep[v][l], d);
else len_to_dep[v][l] = d;
}
}
}
if(len_to_dep[v].count(k)>0) ans = min(ans, len_to_dep[v][k]);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
vector<pi> h(n-1);
for(auto &[a,b] : h) cin >> a >> b;
for(int i = 0; i < n-1; ++i){
int x; cin >> x;
g[h[i][0]].push_back({x, h[i][1]});
g[h[i][1]].push_back({x, h[i][0]});
}
dfs_sz(0,-1,0,0);
dfs(0,-1);
if(ans==1e9) ans = -1;
cout << ans << '\n';
return 0;
}