| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1278181 | Robert_junior | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7, mod = 1e9 + 7;
int tin[N], tout[N], d[N], d1[N], sz[N], bc[N], b[N], mn[N], timer;
vector<pair<int, int>>g[N];
int n, k;
void dfs(int v, int p){
sz[v] = 1;
tin[v] = ++timer;
b[tin[v]] = v;
for(auto [to, w] : g[v]){
if(to == p) continue;
d[to] = d[v] + 1;
d1[to] = d1[v] + w;
dfs(to, v);
sz[v] += sz[to];
if(sz[to] > sz[bc[v]]) bc[v] = to;
}
tout[v] = timer;
}
int res = INT_MAX;
vector<int>cl;
void dfs1(int v, int p, bool keep){
for(auto [to, w] : g[v]){
if(to == p || to == bc[v]) continue;
dfs1(to, v, 0);
}
if(bc[v]) dfs1(bc[v], v, 1);
for(auto [to, w] : g[v]){
if(to == p || to == bc[v]) continue;
for(int i = tin[to]; i <= tout[to]; i++){
int u = b[i];
int w = k - d1[v] * 2 + d1[u];
// k - d1[v] =d[u] + d[v] - 2 * d[lca]
res = min(res, d[u] + mn[w] - 2 * d[v]);
}
for(int i = tin[to]; i <= tout[to]; i++){
int u = b[i];
cl.push_back(d1[u]);
mn[d1[u]] = min(mn[d1[u]], d[u]);
}
}
mn[d1[v]] = min(mn[d1[v]], d[v]);
int w = k + d1[v];
res = min(res, mn[w] - d[v]);
cl.push_back(d1[v]);
if(!keep){
for(auto it : cl) mn[it] = 100000000;
cl.clear();
}
}
int H[N][2], L[N];
main(){
cin>>n>>k;
for(int i = 0; i < n - 1; i++){
cin>>H[i][0]>>H[i][1]>>L[i];
}
for (int i = 0; i < n - 1; i++) {
int a = H[i][0], b = H[i][1], c = L[i];
g[a].push_back({b, c});
g[b].push_back({a, c});
}
for(int i = 1; i <= 1000000; i++){
mn[i] = 100000000;
}
dfs(0, 0);
dfs1(0, 0, 0);
cout<<res<<'\n';
}