#include <bits/stdc++.h>
using namespace std;
int N, K, P[100005], rem[100005];
int par[100005][20];
long long ST[400005], lazy[400005];
long long D[100005];
int X[100005], Y[100005], C[100005];
int timer, tin[100005], out[100005], id[100005];
vector<int> adj[100005];
void update(int v, int l, int r, int p, long long val) {
if(l == r) {
ST[v] = val;
lazy[v] = 0;
return;
}
int md = (l + r) / 2;
if(p <= md) update(v * 2, l, (l + r) / 2, p, val);
else update(v * 2 + 1, (l + r) / 2 + 1, r, p, val);
ST[v] = max(ST[v * 2], ST[v * 2 + 1]);
lazy[v] = 0;
}
void prop(int v, int l, int r) {
if(l == r || lazy[v] == 0) return;
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
ST[v * 2] -= lazy[v];
ST[v * 2 + 1] -= lazy[v];
lazy[v] = 0;
}
void update(int v, int l, int r, int lo, int hi, long long val) {
prop(v, l, r);
if(l > hi || r < lo) return;
if(l >= lo && r <= hi) {
ST[v] -= val; lazy[v] += val;
prop(v, l, r); return;
}
update(v * 2, l, (l + r) / 2, lo, hi, val);
update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
ST[v] = max(ST[v * 2], ST[v * 2 + 1]);
}
int query(int v, int l, int r) {
prop(v, l, r);
if(l == r) return l;
if(ST[v * 2] >= ST[v * 2 + 1])
return query(v * 2, l, (l + r) / 2);
return query(v * 2 + 1, (l + r) / 2 + 1, r);
}
void dfs(int v, int p, int dep = 0) {
par[v][0] = p; id[timer] = v;
tin[v] = timer++; update(1, 0, N - 1, tin[v], dep);
for(auto u : adj[v]) {
int nxt = ((X[u] ^ Y[u]) ^ v);
if(nxt == p) continue;
P[nxt] = u; dfs(nxt, v, dep + C[u]);
}
out[v] = timer - 1;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N >> K;
for(int l = 0; l < N - 1; l++) {
cin >> X[l] >> Y[l] >> C[l];
int U = X[l], V = Y[l];
adj[U].push_back(l);
adj[V].push_back(l);
}
for(int l = 1; l <= N; l++) {
///memset(ST, 0, sizeof ST);
///memset(lazy, 0, sizeof lazy);
for(int i = 1; i <= N; i++)
rem[i] = 0;
rem[l] = 1;
long long res = 0; timer = 0; dfs(l, l);
for(int i = 1; i < 20; i++)
for(int j = 1; j <= N; j++)
par[j][i] = par[par[j][i - 1]][i - 1];
for(int i = 0; i < K; i++) {
int A = query(1, 0, N - 1); res += ST[1]; A = id[A];
///cout << ST[1] << " ";
while(rem[A] == 0) {
int B = A;
for(int j = 19; j >= 0; j--) {
if(rem[par[B][j]] == 0)
B = par[B][j];
}
update(1, 0, N - 1, tin[B], out[B], C[P[B]]);
rem[B] = 1;
}
}
cout << res << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1040 ms |
21692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
