This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll long long
const int N = 100'005;
multiset<ll> s[N];
vector<array<int, 2>> adj[N];
void dfs(int i, int par, int parc) {
for (auto [nxt, w] : adj[i]) {
if (nxt == par) continue;
dfs(nxt, i, w);
if (s[i] < s[nxt]) {
swap(s[i], s[nxt]);
}
for (auto j : s[nxt]) {
s[i].insert(j);
}
}
if (adj[i].size() == 1) s[i].insert(0);
ll val = *s[i].begin();
s[i].erase(s[i].begin());
s[i].insert(val - parc);
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
s[j].clear();
}
dfs(i, 0, 0);
ll sum = 0;
int cnt = 0;
for (auto j : s[i]) {
if (cnt == k) break;
sum += j;
cnt++;
}
cout << -sum << '\n';
}
return 0;
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |