#include <bits/stdc++.h>
using namespace std;
template<typename T>
using V = vector<T>;
typedef pair<int, int> pii;
typedef long long ll;
ll INF;
struct Seg {
Seg *left = nullptr, *right = nullptr;
int l, r, mid;
int val = 0;
bool sparse = false;
Seg(int l, int r) : l(l), r(r) ,mid((r + l) / 2) {
}
void push() {
if (!sparse) {
if (r - l > 1 ) {
left = new Seg(l,mid);
right = new Seg(mid,r);
}
sparse = true;
}
}
void add(int x, int u) {
push();
if (r - l <= 1) {
val += u;
return;
}
if (x < mid)
left->add(x,u);
else
right->add(x,u);
val = left->val + right->val;
}
int q(int a, int b) {
push();
if (b <= l || a >= r) return 0;
if (a <= l && b >= r) return val;
return left->q(a,b) + right->q(a,b);
}
};
vector<int> vals;
map<int, int> to;
struct SegPoint {
Seg *seg;
SegPoint() {
seg = new Seg(0, vals.size());
if (!to.empty()) return;
std::sort(vals.begin(), vals.end());
int id = 0;
for (auto x : vals) {
to[x] = id++;
}
}
void add(int x, int u) {
if (to.count(x) == 0) exit(5);
seg->add(to[x], u);
}
int q(int a, int b) {
if (to.count(a) == 0) exit(5);
if (to.count(b) == 0) exit(5);
return seg->q(to[a],to[b]);
}
};
vector<vector<pii>> G;
vector<bool> is_removed;
vector<int> subsize;
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;
vector<ll> ans, res, jumpw, parw;
vector<int> depth, jump, par;
vector<SegPoint*> st;
void dfs1(SegPoint* stt, int v, int p, int d, int child, int S) {
depth[v] = d;
res[v] = 0;
if(p != -1) {
if(depth[jump[p]] - depth[p] == depth[jump[jump[p]]] - depth[jump[p]])
jump[v] = jump[jump[p]], jumpw[v] = jumpw[jump[p]] + jumpw[p] + parw[v];
else
jump[v] = p, jumpw[v] = parw[v];
}
for(auto [u, w] : G[v]) {
if(u == p || is_removed[u])
continue;
par[u] = v, parw[u] = w;
if(p == -1)
st[u] = new SegPoint();
dfs1(stt, u, v, d + 1, p==-1?u:child, S);
}
if (p == -1) return;
int a = v;
ll s = 0;
ans[v] += res[v] * (S - subsize[child]);
while(jump[a] != a && s + parw[a] <= k) {
if(jumpw[a] + s <= k)
s += jumpw[a], a = jump[a];
else
s += parw[a], a = par[a];
}
if(jump[a] == a) {
stt->add(k - s, res[v] + 1);
st[child]->add(k - s, res[v] + 1);
}
else
res[a] += res[v] + 1;
}
void dfs2(SegPoint* 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 = stt->q(s, s + w) - st[child]->q(s, s + w);
ans[v] += refuel * subsize[u];
stt->add(s + k, refuel);
dfs2(stt, u, v, s + w, child);
stt->add(s + k, -refuel);
}
}
void dfs0(int v, int p, ll s = 0){
vals.push_back(s);
for(auto [u, w] : G[v]){
if(u == p || is_removed[u])
continue;
dfs0(u, v, s + w);
}
}
void centroid_decomp(int v, bool pre) {
int centroid = get_centroid(v, get_subtree_size(v));
if(pre) {
dfs0(centroid, -1);
}
else {
SegPoint *stt = new SegPoint();
jump[centroid] = centroid;
jumpw[centroid] = 0;
dfs1(stt, centroid, -1, 0, 0, get_subtree_size(centroid));
stt->add( 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, pre);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n >> k;
INF = ll(n) * ll(k);
G.resize(n);
is_removed.resize(n);
subsize.resize(n);
par.resize(n);
parw.resize(n);
jump.resize(n);
jumpw.resize(n);
ans.resize(n);
res.resize(n);
depth.resize(n);
st.resize(n);
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(0, 1);
is_removed.clear();
is_removed.resize(n);
centroid_decomp(0, 0);
for(int i = 0; i < n; i++)
cout << ans[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
336 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
336 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
3355 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
336 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
336 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
336 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
336 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
