#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
constexpr int N = 7e4;
ll INF;
struct Vertex {
Vertex* l, * r;
int sum;
Vertex(ll val) : l(nullptr), r(nullptr), sum(val) {}
Vertex(Vertex* l, Vertex* r) : l(l), r(r), sum(0) {
if (l) sum += l->sum;
if (r) sum += r->sum;
}
void extend(){
if(!l)
l = new Vertex(0);
if(!r)
r = new Vertex(0);
}
};
int get_sum(Vertex* v, ll tl, ll tr, ll l, ll r) {
if (l + 1 > r)
return 0;
if (l == tl && tr == r)
return v->sum;
if(v->l == nullptr)
return 0;
ll tm = (tl + tr) / 2;
return get_sum(v->l, tl, tm, l, min(r, tm))
+ get_sum(v->r, tm, tr, max(l, tm), r);
}
void update(Vertex* v, ll tl, ll tr, ll pos, int new_val) {
if (tl + 1 == tr){
v->sum += new_val;
return;
}
v->extend();
ll tm = (tl + tr) / 2;
if (pos < tm)
update(v->l, tl, tm, pos, new_val);
else
update(v->r, tm, tr, pos, new_val);
v->sum = v->l->sum + v->r->sum;
}
vector<pii> G[N];
bool is_removed[N];
int subsize[N];
int get_subtree_size(int v, int p = -1) {
subsize[v] = 1;
for (auto [u, w] : G[v]) {
if (u == p || is_removed[u]) { continue; }
subsize[v] += get_subtree_size(u, v);
}
return subsize[v];
}
int get_centroid(int v, int S, int p = -1) {
for (auto [u, w] : G[v]) {
if (u == p || is_removed[u]) { continue; }
if (subsize[u] * 2 > S) {
return get_centroid(u, S, v);
}
}
return v;
}
int k;
ll ans[N], res[N];
Vertex* st[N];
void dfs1(Vertex* stt, int v, int p, int d, int child, int S, vector<pii>& path) {
res[v] = 0;
for(auto [u, w] : G[v]) {
if(u == p || is_removed[u])
continue;
if(p == -1)
st[u] = new Vertex(0);
path.push_back({path.back().first + w, u});
dfs1(stt, u, v, d + 1, p==-1?u:child, S, path);
path.pop_back();
}
if(p != -1) {
ans[v] += res[v] * (S - subsize[child]);
auto it = lower_bound(path.begin(), path.end(), pair(path.back().first - k, -1));
auto [s, a] = *it;
if(s == 0) {
update(stt, 0, INF, k - path.back().first, res[v] + 1);
update(st[child], 0, INF, k - path.back().first, res[v] + 1);
}
else
res[a] += res[v] + 1;
}
}
void dfs2(Vertex* stt, int v, int p, ll s, int child) {
for(auto [u, w] : G[v]) {
if(u == p || is_removed[u])
continue;
if(p == -1)
child = u;
int refuel = get_sum(stt, 0, INF, s, s + w);
refuel -= get_sum(st[child], 0, INF, s, s + w);
ans[v] += refuel * subsize[u];
update(stt, 0, INF, s + k, refuel);
dfs2(stt, u, v, s + w, child);
update(stt, 0, INF, s + k, -refuel);
}
}
void centroid_decomp(int v = 0) {
int centroid = get_centroid(v, get_subtree_size(v));
Vertex* stt = new Vertex(0);
vector<pii> path = {{0, centroid}};
dfs1(stt, centroid, -1, 0, 0, get_subtree_size(centroid), path);
update(stt, 0, INF, k, 1);
dfs2(stt, centroid, -1, 0, 0);
is_removed[centroid] = true;
for (auto [u, w] : G[centroid]) {
if (is_removed[u])
continue;
centroid_decomp(u);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n >> k;
INF = ll(n) * ll(k);
for(int i = 0; i < n - 1; i++) {
int u, v, l;
cin >> u >> v >> l;
G[u].push_back({v, l});
G[v].push_back({u, l});
}
centroid_decomp();
for(int i = 0; i < n; i++)
cout << ans[i] << '\n';
}
Compilation message
Main.cpp: In function 'int get_subtree_size(int, int)':
Main.cpp:61:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | for (auto [u, w] : G[v]) {
| ^
Main.cpp: In function 'int get_centroid(int, int, int)':
Main.cpp:69:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
69 | for (auto [u, w] : G[v]) {
| ^
Main.cpp: In function 'void dfs1(Vertex*, int, int, int, int, int, std::vector<std::pair<int, int> >&)':
Main.cpp:86:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
86 | for(auto [u, w] : G[v]) {
| ^
Main.cpp:97:61: error: missing template arguments before '(' token
97 | auto it = lower_bound(path.begin(), path.end(), pair(path.back().first - k, -1));
| ^
Main.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
98 | auto [s, a] = *it;
| ^
Main.cpp: In function 'void dfs2(Vertex*, int, int, ll, int)':
Main.cpp:109:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
109 | for(auto [u, w] : G[v]) {
| ^
Main.cpp: In function 'void centroid_decomp(int)':
Main.cpp:135:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
135 | for (auto [u, w] : G[centroid]) {
| ^
