Dynamic Tree Vertex Add Subtree Sum

A query for an edge $(v,p)$ asks for the sum of the connected component containing $v$ after temporarily removing that edge.

Maintain a Link-Cut Tree. For every node, store its own value, the aggregate of its auxiliary splay children, and the aggregate of its virtual children outside the current preferred paths. During access, when the right child changes between a preferred child and a virtual child, update the virtual aggregate accordingly. Then after makeroot(x) and access(x), the aggregate stored at $x$ is the sum of the whole represented-tree component containing $x$.

Thus a query of type 0 is handled by cut and link, a query of type 1 by a point addition, and a query of type 2 by cut(v,p), reading the component sum of $v$, and link(v,p). Each operation takes $O(\log N)$ amortized time.

Solution written by GPT5.5