#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
#define ll long long
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
const ll m = 1e15; // !
int t, h[N], n, k, f[N], ri_[N * 30], le_[N * 30], mx[N][2], idx, b[N];
ll sum[N], ans[N];
struct node {
ll s;
int c;
} tree[N * 30];
pii p[N];
vector<pii> V[N], x;
void dfs(int u) {
x.push_back({h[u], u});
for(int i = 0; i < V[u].size(); i++) {
if(V[u][i].f == p[u].f) continue;
p[V[u][i].f] = {u, V[u][i].s};
h[V[u][i].f] = h[u] + V[u][i].s;
dfs(V[u][i].f);
}
}
int up(int u) {
int sum = 0;
while(f[u]) {
sum += p[u].s;
f[u] = 0;
u = p[u].f;
}
return sum;
}
int get(int u,ll l, ll r, int k) {
if(l == r) {
return k * l;
}
int mid = (l + r) >> 1;
if(tree[ri_[u]].c >= k) return get(ri_[u], mid + 1, r, k);
return tree[ri_[u]].s + get(le_[u], l, mid, k - tree[ri_[u]].c);
}
void upd(int u,ll id, ll l,ll r,int val) {
if(l == r) {
tree[u].c += val;
tree[u].s += val * l;
return;
}
int mid = (l + r) >> 1;
if(id <= mid) {
if(!le_[u]) le_[u] = ++idx;
upd(le_[u], id, l, mid, val);
}
else {
if(!ri_[u]) ri_[u] = ++idx;
upd(ri_[u], id, mid + 1, r, val);}
tree[u].c = tree[le_[u]].c + tree[ri_[u]].c;
tree[u].s = tree[le_[u]].s + tree[ri_[u]].s;
}
void dfs2(int u) {
int M = 0, y = 0;
for(int i = 0; i < V[u].size(); i++) {
if(V[u][i].f == p[u].f) continue;
dfs2(V[u][i].f);
int v = V[u][i].f;
if(mx[u][0] < mx[v][0] + V[u][i].s) {
mx[u][1] = mx[u][0];
mx[u][0] = mx[v][0] + V[u][i].s;
} else mx[u][1] = max(mx[u][1], mx[v][0] + V[u][i].s);
}
}
void reroot(int u, int p_ = -mod) {
ans[u] = get(1, 1, m, k);
for(int i = 0; i < V[u].size(); i++) {
if(V[u][i].f == p[u].f) continue;
//
int v = V[u][i].f;
// mx[v][0] - V[u][i].s gaxdeba
int x = mx[u][0];
if(mx[v][0] + V[u][i].s == mx[u][0]) x = mx[u][1];
x = max(x, p_);
upd(1, mx[v][0] + V[u][i].s, 1, m, -1);
upd(1, mx[v][0], 1, m, 1);
upd(1, x, 1, m, -1);
upd(1, x + V[u][i].s, 1, m, 1);
// return;
reroot(v, x + V[u][i].s);
upd(1, mx[v][0] + V[u][i].s, 1, m, 1);
upd(1, mx[v][0] , 1, m, -1);
upd(1, x, 1, m, 1);
upd(1, x + V[u][i].s, 1, m, -1);
}
}
main(){
cin >> n >> k;
idx = 1;
for(int i = 2; i <= n; i++) {
int u, v, w;
cin >> u >> v >> w;
V[u].push_back({v, w});
V[v].push_back({u, w});
f[i] = 1;
}
dfs(1);
sort(x.rbegin(), x.rend());
for(int i = 0; i < x.size(); i++) {
sum[x[i].s] = up(x[i].s);
upd(1, sum[x[i].s], 1, m, 1);
// cout << x[i].s <<" __" << sum[x[i].s] << " ";
}
dfs2(1);
reroot(1);
for(int i = 1; i <= n; i++) cout << ans[i] <<"\n";
}
Compilation message
Main.cpp: In function 'void dfs(int)':
Main.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'void dfs2(int)':
Main.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
Main.cpp:61:6: warning: unused variable 'M' [-Wunused-variable]
61 | int M = 0, y = 0;
| ^
Main.cpp:61:13: warning: unused variable 'y' [-Wunused-variable]
61 | int M = 0, y = 0;
| ^
Main.cpp: In function 'void reroot(int, int)':
Main.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
99 | main(){
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:112:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int i = 0; i < x.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
339 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
