#include <iostream>
#include <vector>
using namespace std;
#define ii pair <int, int>
#define fi first
#define se second
const int N = 2e5 + 10;
const int M = 1e6 + 10;
int n, k, x, y, w;
vector <ii> v[N];
int sz[N], dis[M];
bool solved[N];
int calc_size(int s, int p = -1) {
sz[s] = 1;
for (ii z: v[s]) {
if (z.fi == p || solved[z.fi]) continue;
sz[s] += calc_size(z.fi, s);
}
return sz[s];
}
int FindCentroid(int s, int Size, int p = -1) {
for (ii z: v[s]) {
if (z.fi == p || solved[z.fi]) continue;
if (sz[z.fi] > Size) return FindCentroid(z.fi, Size, s);
}
return s;
}
int ans = 1e9, mx;
void run(int s, int p, int depth, int len, bool filling) {
if (len > k) return;
mx = max(mx, len);
if (filling) {
if (dis[len] == 0) dis[len] = depth;
else dis[len] = min(dis[len], depth);
} else {
if (dis[k - len] != 0) ans = min(ans, dis[k - len] + depth);
if (len == k) ans = min(ans, depth);
}
for (ii z: v[s]) {
if (z.fi == p || solved[z.fi]) continue;
run(z.fi, s, depth + 1, len + z.se, filling);
}
}
void CentroidDecomp(int s = 1) {
int cen = FindCentroid(s, calc_size(s) >> 1);
solved[cen] = true;
mx = 0;
for (ii z: v[cen]) {
if (solved[z.fi]) continue;
run(z.fi, cen, 1, z.se, false);
run(z.fi, cen, 1, z.se, true);
}
fill_n(dis, mx + 1, 0);
for (ii z: v[cen]) {
if (solved[z.fi]) continue;
CentroidDecomp(z.fi);
}
}
int best_path(int NN, int KK, int H[][2], int L[]) {
n = NN;
k = KK;
for (int i = 0; i < n - 1; ++i) {
x = H[i][0], y = H[i][1], w = L[i];
++x, ++y;
v[x].push_back(ii(y, w));
v[y].push_back(ii(x, w));
}
CentroidDecomp();
if (ans == 1e9) ans = -1;
return ans;
}
//「名前だけで、どうやって君のことを覚えていられるの?」
//「結局、君の名前さえちゃんと分からないんだ?」
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |