$$$O(1)$$$ per update and query.

Let's root the tree. We have the value $$$a_i$$$ of every node that we want to support. Let's also define $$$b_i$$$ for every node, initially $$$0$$$, and this will denote the sum of values of $$$i$$$'s children.

Therefore, on an update $$$(v, x)$$$ we add $$$x$$$ to $$$a_v, b_{p_v}$$$, and on a query $$$v$$$ we return $$$b_v + a_{p_v}$$$. Everything is $$$O(1)$$$. The similarity to the segment tree optimization is that, we transformed from updating $$$1$$$ element and querying $$$O(n)$$$ elements, to updating $$$2$$$ elements and querying $$$2$$$ elements.

$$$O(\sqrt{E})$$$ per update and query. If you ask me, this is cool, but not very good. Generally this can get up to $$$O(V)$$$.

This follows the general vibe of square root decomposition. Let's fix some boundary value $$$K$$$, and call a vertex "heavy" if it has more than $$$K$$$ neighbors, otherwise "light". We will maintain the values $$$a_i$$$ as we run, and also maintain $$$b_i$$$ for each heavy vertex $$$i$$$, which will be the answer once we query on it.

For every vertex, maintain a list of its heavy neighbors, and observe that it is of size at most $$$\frac{2E}{K}$$$, since the sum of degrees is at most $$$2E$$$. On an update $$$(v, x)$$$, add $$$x$$$ to $$$a_v$$$, and to $$$b_u$$$ for every heavy neighbor $$$u$$$ of $$$v$$$. On a query, if it is on a light vertex, iterate over all the neighbors and sum $$$a_u$$$, and if it is on a heavy vertex, return $$$b_v$$$.

Updates take at most $$$O(\frac{E}{K})$$$, and queries take at most $$$O(K)$$$. If we want to minimize their maximum, then by choosing $$$K = \sqrt{E}$$$ we obtain $$$O(\sqrt{E})$$$ on both.

Flows.

Suppose we want to check whether we can direct edges s.t $$$\max |T_i| \leq k$$$. Create a bipartite graph, with $$$E$$$ vertices on the left side and $$$V$$$ vertices on the right side. We will also have a source $$$S$$$ and sink $$$T$$$.

• For every vertex $$$e$$$ on the left side, add an edge $$$S \to e$$$ with capacity $$$1$$$.
• For every vertex $$$e$$$ on the left side, corresponding to the edge $$$(u, v)$$$, add two edges of capacity $$$1$$$ from $$$e$$$ to $$$u$$$ and to $$$v$$$ on the right side.
• For every vertex $$$v$$$ on the right side, add an edge $$$v \to T$$$ with capacity $$$k$$$.

Now, if the maximum flow on this graph is $$$|E|$$$, then we have successfully directed every edge so that $$$|T_i| \leq k$$$ (the directions can be deduced from the flow), and otherwise, we need to increase $$$k$$$.

The simplest way to do this is with ford-fulkerson, while incrementing $$$k$$$ by $$$1$$$ every time it is necessary, for a total complexity of $$$O(E^2)$$$.

You can also binary search on $$$k$$$, and use Dinic's. This should end up being $$$O(E \sqrt{E} \log E)$$$, with a similar analysis to how Dinic's performs on bipartite graphs.

Another nice part about this is that, we don't really want to minimize $$$\max |T_i|$$$, but rather upto a constant factor, since it only plays part as asymptotics (well, at least I don't care about minimizing it). If we're willing to minimize it up to factor $$$2$$$, then instead of binary searching with arithmetic mean, we can binary search with geometric mean, for $$$O(\log \log E)$$$ iterations: indeed, after one iteration we know the answer upto a factor of $$$\sqrt{E}$$$. In general, after $$$t$$$ iterations we know the answer upto a factor of $$$E^{2^{-t}}$$$, and when $$$t = \log \log E$$$:

.

For a subset of vertices $$$S \subseteq V$$$, define $$$e_S$$$ as the number of edges in the subgraph, induced by $$$S$$$. Then the minimum achievable value is:

In particular, in a tree all subgraphs contain strictly less edges than vertices, so this value is $$$1$$$. Also, in a graph that has no cycles of length upto $$$2k$$$, the number of edges is $$$O(V^{1 + \frac{1}{k}})$$$, and since this applies to all of its subgraphs, this value is at most $$$O(V^{\frac{1}{k}})$$$ (link)

We will use the definition in the formula spoiler above, and the flow algorithm mentioned above. Define $$$k = d(G)$$$. First, the answer cannot be less than $$$k$$$, because otherwise there exists $$$S \subseteq V$$$ such that $$$ans \cdot |S| < e_S$$$, which is impossible from pigeonhole principle.

Now let's prove that this $$$k$$$ suffices. On the maximum flow graph, let's show that the minimum cut is at least $$$|E|$$$. We will observe every cut as its left side: the source $$$S$$$, a subset of the left side $$$L$$$, and a subset of the right side $$$R$$$. The cut for such $$$(L, R)$$$ is:

Let's fix $$$R$$$ and find the best $$$L$$$. Every vertex in $$$L$$$ has 2 outgoing edges to 2 endpoints on the right side. You can see that, if both endpoints are in $$$R$$$ then it's strictly better to include this vertex in $$$L$$$. If one endpoint is in $$$R$$$ then it doesn't matter, and if $$$0$$$ points are in $$$R$$$ then it's strictly worse to include this vertex. So let's take $$$L$$$ as the subset of vertices whose both endpoints are in $$$R$$$. If you think of $$$R$$$ as a subset of vertices in the original graph, then $$$L$$$ is the subset of edges in the induced subgraph. So:

Hence, for all $$$R$$$, the best $$$L$$$ provides a cut of size at least $$$|E|$$$, so all cuts are at least $$$|E|$$$.

Repeatedly find a vertex of minimum degree, direct all of its edges outwards, and remove it (and its edges). To implement this in linear time, create lists $$$b_0, \ldots, b_{n-1}$$$, and put all vertices of degree $$$i$$$ in $$$b_i$$$. Maintain a pointer to the first nonempty list. Iteratively, pop a vertex from this list, direct all of its edges that lead to vertices we have yet to visit, and for every such vertex, subtract $$$1$$$ from its degree and move it to its new list. After that, subtract $$$1$$$ from the pointer, and then increment it until another nonempty list is found.

You don't actually have to remove a vertex from its current list, just mark vertices as visited whenever you work on them, and when you pop a vertex from a list, if it's visited then ignore it.

Proof of approximation follows from the fact that, any induced subgraph of $$$G$$$ (by vertex set $$$S$$$) has average degree $$$\frac{2e_S}{|S|} \leq 2d(G)$$$, thus at every step we choose a vertex of degree at most $$$2d(G)$$$ (since it's of minimum degree).

I'll try to be rigorous so this might be a bit slow.

For simplicity, suppose we are given $$$n$$$ elements and $$$n$$$ subsets (or alternatively assume we want to solve this case). We can be given $$$2^{n^2}$$$ inputs, and each of them requires a different construction: indeed, let there be two different inputs. Then there exist $$$i,j$$$ such that in one of them, subset $$$i$$$ contains element $$$j$$$, and in the other it doesn't. Suppose towards contradiction that we can give them the same construction. In this construction we can update subset $$$i$$$ with $$$1$$$, and then query subset $$$j$$$. The output cannot be both $$$0$$$ and $$$1$$$, to fit both inputs.

Thus, we need to show $$$2^{n^2}$$$ different constructions. Fix a function $$$f(n)$$$ such that we want all resulting update and query subsets, to be of size upto $$$f(n)$$$ (for the final complexity to be $$$O(f(n))$$$). Let's see how many constructions there can be for $$$N$$$ new elements:

Each of the $$$2n$$$ subsets ($$$n$$$ query and $$$n$$$ update) has $$$\binom{N}{f(n)} \leq N^{f(n)}$$$ ways to be selected, for a total upperbound of $$$\left( {N^{f(n)}} \right) ^{2n} = N^{2nf(n)} = 2^{\log_2 (N) 2nf(n)}$$$.

For different inputs we can choose different $$$N$$$, but this is negligible — suppose all our constructions work with $$$N$$$ bounded by some polynomial $$$p(n)$$$. Hence for large enough $$$n$$$, we have $$$\log_2 N \leq c \log_2 n$$$ (for some constant $$$c$$$). So the total number of constructions, summed up for all $$$N$$$ from $$$1$$$ to $$$p(n)$$$, is upperbounded by:

for some constant $$$c$$$, and must exceed $$$2^{n^2}$$$. Comparing the exponents, there exists a constant $$$d$$$ such that:

If we pretend that $$$N$$$ being super-polynomial in $$$n$$$ is not a problem, then don't forget that while the lowerbound is $$$\frac{n}{d \log N}$$$, we also require $$$\log N$$$ work to resolve accesses to such an enormous amount of memory (and yes, technically we also need $$$O(\log n)$$$ time to access an array of size $$$n$$$, so our lowerbound is even worse, but we can sweep this under the rug like any other algorithm).

Fix $$$L$$$ (it's going to be very small). For every subset of indicies in $$$[0, L)$$$, we're going to keep the sum of elements in this subset. Similarly, we'll do this for every subset of indicies in $$$[L, 2L), [2L, 3L)$$$ and so on.

Upon an update $$$(i, x)$$$, we find the block of size $$$L$$$ containing $$$i$$$, and for every subset in there containing $$$i$$$ we add $$$x$$$. This works in $$$O(2^L)$$$.

Upon a query $$$j$$$, we break subset $$$j$$$ (during preprocessing) to $$$\frac{n}{L}$$$ parts, one for each block of size $$$L$$$. Then it remains to sum $$$\frac{n}{L}$$$ values.

We want to minimize the maximum of $$$2^L, \frac{n}{L}$$$. Choosing anything like $$$L = c \log n$$$ for $$$c > 1$$$ works, for simplicity you can choose $$$c = 2$$$ and obtain the wanted runtime (and even $$$c = 3$$$ for less memory consumption!).