// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
template<int SZ> struct Tree {
int n;
vector<pair<int,int>> adj[SZ];
void init(int N, int H[][2], int L[]) {
n = N;
for (int i = 0; i < n-1; i++) {
int a, b, c; cin >> a >> b >> c;
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
}
};
const int maxn = 200000;
int n, k;
int sz[maxn], dpth[maxn], ldpth[maxn];
Tree<maxn> tree;
unordered_map<int,int> m[maxn];
int ans = INT_MAX;
int dfs(int nd, int par, int l) {
sz[nd] = 1, dpth[nd] = dpth[par] + 1; ldpth[nd] = l;
for (auto i : tree.adj[nd])
if (i.first != par)
sz[nd] += dfs(i.first, nd, l + i.second);
return sz[nd];
}
inline int mget(int nd, int dist) {
// dist to find = ldist[nd] + dist;
dist += ldpth[nd];
if (m[nd].find(dist) == m[nd].end()) return INT_MAX;
return m[nd][dist];
}
inline void upd_min(int nd, int k, int v) {
if (m[nd].find(k) == m[nd].end()) {m[nd][k] = v; return; }
// cout << "Y " << nd << ' ' << k << ' ' << (m[nd].find(k) == m[nd].end()) << ' ' << m[nd][k] << ' ';
m[nd][k] = min(m[nd][k], v);
// cout << m[nd][k] << endl;
}
void msl(int nd, int par) {
for (auto i : tree.adj[nd])
if (i.first != par)
msl(i.first, nd);
int hch = -1, hb = -1;
for (auto i : tree.adj[nd])
if (i.first != par)
if (hch == -1 || hb < sz[i.first])
hch = i.first, hb = sz[i.first];
// cout << "Z " << nd << ' ' << (hch == -1) << endl;
if (hch == -1) {m[nd][ldpth[nd]] = dpth[nd];
// cout << "---------" << endl << nd << endl;
// cout << "X ";
// for (auto i : m[nd]) cout << i.first << ' ' << i.second << ' ';
// cout << endl;
return;}
// cout << "----" << endl;
swap(m[nd], m[hch]);
// cout << nd << endl;
for (auto i : tree.adj[nd])
if (i.first != par && i.first != hch)
for (auto j : m[i.first]) {
// cout << j.first << ' ' << j.second << endl;
// (dist[i], dpth[i]) --> (dist[i] - dist[nd], dpth[i] - dpth[nd])
int val = mget(nd, k - (j.first - ldpth[nd]));
if (val != INT_MAX)
ans = min(ans, j.second + mget(nd, k - (j.first - ldpth[nd])) - 2*dpth[nd]);
// if (val != INT_MAX)
// cout << nd << ' ' << j.first << ' ' << j.second << ' ' << j.second + mget(nd, k - (j.first - ldpth[nd])) - 2*dpth[nd] << endl;
upd_min(nd, j.first, j.second);
}
// cout << nd << ' ' << mget(nd, k) - dpth[nd] << endl;
// cout << "X ";
// for (auto i : m[nd]) cout << i.first << ' ' << i.second << ' ';
// cout << endl;
ans = min(ans, mget(nd, k) - dpth[nd]);
upd_min(nd, ldpth[nd], dpth[nd]);
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
tree.init(n, H, L);
dfs(0, 0, 0);
msl(0, 0);
return ans;
}
// #define LOCAL
// #define CODEFORCES
// signed main() {
// #ifndef LOCAL
// cin.tie(nullptr) -> ios::sync_with_stdio(false);
// #endif
// #ifdef LOCAL
// freopen("main.in", "r", stdin);
// #endif
// int t;
// #ifdef CODEFORCES
// cin >> t;
// #endif
// #ifndef CODEFORCES
// t=1;
// #endif
// while(t--) solve();
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15956 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15932 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
15956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15956 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15932 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
15956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15956 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15932 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
15956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15956 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15932 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
15956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
