$$$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 constant factor of $$$\sqrt{E}$$$. In general, after $$$t$$$ iterations we know the answer upto a constant 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}})$$$, hence 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 = \left\lceil \max_{\emptyset \neq S \subseteq V} \frac{e_S}{|S|} \right\rceil$$$. 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|$$$.

Let's take some ordering of the edges, and direct them greedily one by one, while maintaining for each vertex the number of outgoing edges we gave it. So initially each vertex has $$$0$$$ outgoing edges, then for every edge, if one endpoint has less outgoing edges, then direct it towards the other endpoint. If both endpoints have the same number, assign it arbitrarily.

I couldn't upperbound the complexity, but I did find that you can construct (with induction), a tree of size $$$2^k$$$ that has an ordering of edges in which we have a vertex with $$$k$$$ outgoing edges (while trees can be ordered to have $$$1$$$ per vertex). So this has a multiplicative factor of at least $$$O(\log n)$$$.

Another interesting idea would be to choose the initial ordering uniformly in random. Perhaps the expected factor becomes smaller, like $$$O(\log \log n)$$$.

During updates and queries, we will change directions of edges. Observe that changing the direction of a single edge requires $$$O(1)$$$ work to update all our data: we just need to update $$$b_u, b_v$$$, and the outgoing edges lists of $$$u, v$$$.

Let's choose some arbitrary initial directions of all edges. Whenever a query or update is called on a vertex, first flip all of its outgoing edges inwards, then do the operation on this vertex (that now has $$$0$$$ outgoing neighbors) — so after the operation, this vertex has $$$0$$$ outgoing edges (hence another operation on this vertex is $$$O(1)$$$).

I have more faith in this approach, but I didn't even test it in practice. What I observed is that an adversary can choose a sequence of operations, to make us do on average $$$\left\lceil \max_{\emptyset \neq S \subseteq V} \frac{e_S}{|S|} \right\rceil$$$ per operation — if the adversary finds the worst subset of vertices $$$S = \lbrace v_1, \ldots, v_m \rbrace$$$ then it can do operations on every vertex of $$$S$$$, in cyclic order.

However, the adversary doesn't necessarily use this worst subset against us, and additionally I didn't find a counterexample like the one for the greedy approach (that adds a non-constant multiplicative factor).