/*
Code written by Talant I.D.
*/
#include <bits/stdc++.h>
//~ #include <ext/pb_ds/assoc_container.hpp>
//~ using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
//~ typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) ll((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
const ll mod = 998244353 ;
ll mode(ll a) {
a %= mod;
while (a < 0) {
a += mod;
}
return a;
}
ll subt(ll a, ll b) {
return mode(mode(a)-mode(b));
}
ll add(ll a, ll b) {
return mode(mode(a)+mode(b));
}
ll mult(ll a, ll b) {
return mode(mode(a)*mode(b));
}
ll binpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b&1) res = mult(res, a);
a = mult(a, a);
b >>= 1;
}
return res;
}
const int N = 1e5+7;
vector <pair <int, ll>> graph[N];
int n, k;
//~ int timer, tin[N], tout[N], up[N][20];
pii down[N];
//~ bool upper(int a, int b) {
//~ return tin[a] <= tin[b] && tout[a] >= tout[b];
//~ }
//~ int get_lca(int a, int b) {
//~ if (upper(a, b)) return a;
//~ if (upper(b, a)) return b;
//~ for (int i = 19; i >= 0; i--) {
//~ if (!upper(up[a][i], b)) {
//~ a = up[a][i];
//~ }
//~ }
//~ return up[a][0];
//~ }
multiset <ll, greater <ll>> st;
pii dfs(int v, int p) {
//~ up[v][0] = p;
//~ for (int i = 1; i < 20; i++) {
//~ up[v][i] = up[up[v][i-1]][i-1];
//~ }
//~ tin[v] = ++timer;
ll mx = 0, ind = v, from = v;
for (auto to : graph[v]) {
if (to.first == p) continue;
auto ans = dfs(to.first, v);
if (mx < to.second+ans.first) {
mx = to.second+ans.first;
ind = ans.second;
from = to.first;
}
}
down[v] = mp(ind, from);
//~ tout[v] = ++timer;
return mp(mx, ind);
}
void dfs2(int v, int p, ll len = 0) {
int children = 0;
for (auto to : graph[v]) {
if (to.first == p) continue;
if (to.first == down[v].second) {
dfs2(to.first, v, len+to.second);
}
else {
dfs2(to.first, v, to.second);
}
children++;
}
if (children == 0) {
st.insert(len);
}
}
int main() {
do_not_disturb
cin >> n >> k;
ll sum = 0;
int leaves = 0;
for (int i = 0; i < n-1; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
sum += c;
graph[a].pb(mp(b, c));
graph[b].pb(mp(a, c));
}
for (int i = 1; i <= n; i++) {
if (sz(graph[i]) == 1) {
leaves++;
}
}
if (k >= leaves) {
for (int i = 1; i <= n; i++) {
cout << sum << endl;
}
return 0;
}
for (int i = 1; i <= n; i++) {
//~ timer = 0;
dfs(i, i);
dfs2(i, i);
int q = k;
ll ans = 0;
while (sz(st) && q--) {
ans += *st.begin();
st.erase(st.begin());
}
st.clear();
cout << ans << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
10884 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
