| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1309003 | Nomio | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define ss second
#define ff first
#define pii pair<int, int>
using namespace std;
using ll = long long;
vector<vector<pii>> adj;
vector<int> sz, dis, path;
vector<bool> removed;
int s = 0, ans = 1e9, mx, K;
int get_sz(int u, int p) {
sz[u] = 1;
for(pii P : adj[u]) {
int v = P.ff;
if(removed[v] || v == p) continue;
sz[u] += get_sz(v, u);
}
return sz[u];
}
int get_centroid(int u, int p, int sze) {
for(pii P : adj[u]) {
int v = P.ff;
int w = P.ss;
if(removed[v] || v == p) continue;
if(sz[v] > sze / 2) return get_centroid(v, u, sze);
}
return u;
}
vector<pii> vec;
void get_path(int u, int p, int dist, int depth) {
if(dist > K) return;
mx = max(mx, dist);
path[dist] = min(path[dist], depth);
vec.push_back({dist, depth});
for(pii P : adj[u]) {
int v = P.ff;
int w = P.ss;
if(v == p || removed[v]) continue;
get_path(v, u, dist + w, depth + 1);
}
}
void solve(int u) {
get_sz(u, -1);
int center = get_centroid(u, -1, sz[u]);
removed[center] = 1;
mx = 0;
path[0] = 0;
for(pii P : adj[center]) {
int v = P.ff;
int w = P.ss;
if(removed[v]) continue;
get_path(v, center, w, 1);
for(pii P : vec) {
int dist = P.ff;
int depth = P.ss;
ans = min(ans, depth + path[K - dist]);
}
for(pii P : vec) {
int dist = P.ff;
int depth = P.ss;
path[dist] = min(path[dist], depth);
}
}
fill(path.begin(), path.begin() + mx + 1, 0);
for(pii P : adj[center]) {
int v = P.ff;
int w = P.ss;
if(removed[v]) continue;
solve(v);
}
}
int best_path(int n, int k, int H[][2], int L[]) {
K = k;
for(int i = 0; i < n - 1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
removed.resize(n);
sz.resize(n);
adj.resize(n);
path.resize(k + 1);
solve(0);
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
int H[n][2], L[n];
for(int i = 0; i < n - 1; i++) {
cin >> H[i][0] >> H[i][1];
}
for(int i = 0; i < n - 1; i++) {
cin >> L[i];
}
cout << best_path(n, k, H, L) << '\n';
return 0;
}