#include <bits/stdc++.h>
#define inf 1e16
using namespace std;
long long n, k;
vector<pair<long long,long long>> g[100001];
vector<int> sol;
long long deep[100001], closest[100001];
long long ans;
void dfs(long long node, long long parent, long long lim, long long cost, bool reconst) {
closest[node] = inf;
deep[node] = -inf;
for (auto i : g[node]) {
if (i.first != parent) {
dfs(i.first, node, lim, i.second, reconst);
deep[node] = max(deep[node], deep[i.first] + i.second);
closest[node] = min(closest[node], closest[i.first] + i.second);
}
}
if (deep[node] < 0 && closest[node] > lim) {
deep[node] = 0;
}
if (deep[node] + closest[node] <= lim) {
deep[node] = -inf;
return;
}
if (deep[node] + cost > lim) {
if (reconst) {
sol.push_back(node);
}
ans++;
closest[node] = 0;
deep[node] = -inf;
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> k;
for (long long i = 2; i <= n; ++i) {
long long a, b,w;
cin >> a >> b>>w;
g[a].push_back({ b,w });
g[b].push_back({ a,w });
}
long long st = 0, dr = inf;
long long rep = 0;
while (st <= dr) {
long long mid = (st + dr) / 2;
ans = 0;
dfs(1, 0, mid, 0, 0);
if (ans <= k) {
rep = mid;
dr = mid - 1;
}
else {
st = mid + 1;
}
}
cout << rep << '\n';
dfs(1, 0, rep, 0, true);
vector<bool> seen(n + 1);
for (auto i : sol) {
seen[i] = true;
}
for (int i = 1; i <= n; ++i) {
if ((int)sol.size() == k) {
break;
}
if (!seen[i]) {
sol.push_back(i);
}
}
for (auto i : sol) {
cout << i << ' ';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
48 ms |
14744 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
40 ms |
14648 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
