DMOJ - BOB Equilibrium

Time Complexity: $O(N\log N)$

Using centroid decomposition, we can

• Update the value at some vertex $v$ in $O(\log N)$ time
• Query the sum of the values of all vertices that are distance exactly $d$ away from some vertex $v$ in $O(\log N)$ time.

You can check the second approach for USACO At Large for an explanation of how to do this.

What we need for this problem is slightly different; first we need to process some number of updates of the following form:

• Add 1 to the values of all vertices at most $d$ away from some vertex $v$.

And then output the values at all vertices at the end. We can use prefix sums for this.

(Note: quite close to TL ...)

void ad(vi& a, int b) {
    ckmin(b,sz(a)-1); if (b < 0) return;
    a[b] ++;
}
int get(vi& a, int b) {
    assert(b >= 0 && b < sz(a));
    return a[b]; }
void prop(vi& a) { R0F(i,sz(a)-1) a[i] += a[i+1]; }

vi adj[MX];