DMOJ - Bob Equilibrium

Time Complexity: $\mathcal{O}(N\log N)$

Using centroid decomposition, we can

• Update the value at some vertex $v$ in $\mathcal{O}(\log N)$ time
• Query the sum of the values of all vertices that are distance exactly $d$ away from some vertex $v$ in $\mathcal{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 ...)

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;