The link-cut tree is a data structure that can maintain dynamic forest (that is, we can add/remove edges as long as the graph remains a forest) and handle various types of queries efficiently. It can handle not only path aggregation/update queries but also subtree aggregation queries. Let's go further and try subtree lazy propagation !

Note that there is a limitation of the lazy propagation operator to be used in this link-cut tree trick : invertibility. For example, subtree add query meets this condition, but subtree bitwise-or update doesn't.

Alternative ways

The top tree can perform subtree update queries quite naturally, without requiring invertibility, but it's a bit hard to implement and has a relatively big constant in running time. The euler tour tree can perform subtree update/aggregation queries efficiently but can't handle path queries.

Terms

auxiliary tree : the splay tree used to represent the original tree, not the original tree itself

Content

As stated above, we can handle any update operators that are invertible, but we will focus on subtree add + subtree sum here. Every node has a variable called added, which denotes the amount of subtree addition on the node.
We can't naively propagate added because the number of children (in original tree) can be huge, so we "pull down" the update information to a single child instead of "pushing down" it to all the children. Roughly, we want to propagate added when we access (some people call it expose), which brings a specific node to the root of the auxiliary tree. When we are doing access and we are at node x, whose parent (in the auxiliary tree) is p, we can apply p.added to x, without touching other children of p.
Now, we have a problem; since we do not propagate added to all the children at once, we can't clear added and we sometimes fetch the same addition from the same parent multiple times. To avoid this, we introduce a new variable cancel on every node. When we apply x.parent.added to x, we set x.cancel to x.parent.added. The next time we apply x.parent.added, we only apply the diff : x.parent.added - x.cancel. This is why we need invertibility.
In this way, we can avoid double addition and achieve the same time complexity as the original link-cut tree since we can propagate in $$$O(1)$$$.
Finally, sum can be properly updated using size information and the 'maintaining subtree information' technique.

Notes

• We never clear added.
• Whenever we change the parent of a node x in the auxiliary tree, we have to set x.cancel to x.parent.added to avoid fetching unnecessary addition from the new parent. This is required even when manipulating heavy edges, so the rotate function will be a bit messy.
• Of course, we can perform path sum/add and similar types of queries at the same time.(haven't implemented yet)

Implementation

Here is some code that is not needed to process subtree sum queries but is needed to process subtree add queries. You can see the whole code here.

	void add(int64_t add_val) {
		val += add_val;
		sum += add_val * size;
		added += add_val;
		light_sum += add_val * light_size;
	}
	void flush() {
		if (p != NONE) {
			add(p->added - cancel);
			cancel = p->added;
		}
		if (rev) {
			std::swap(l, r);
			l->rev ^= 1;
			r->rev ^= 1;
			rev = false;
		}
	}
	void rotate(int dir) {
		Node *new_root = ch[!dir];
		assert(new_root != NONE);
		if (new_root->ch[dir] != NONE) new_root->ch[dir]->flush(); // <---
		ch[!dir] = new_root->ch[dir];
		ch[!dir]->p = this;
		ch[!dir]->cancel = added; // <---
		new_root->ch[dir] = this;
		if (p->l == this) p->l = new_root;
		if (p->r == this) p->r = new_root;
		new_root->p = p;
		new_root->cancel = p->added; // <---
		p = new_root;
		cancel = new_root->added; // <---
		fetch(), new_root->fetch();
	}
	void link(Node *parent) {
		parent->expose();
		expose();
		p = parent;
		cancel = parent->added; // <- Here, we adjust 'cancel' to avoid fetching unnecessary addition
		p->r = this;
		p->fetch();
	}

Problems

• https://judge.yosupo.jp/problem/dynamic_tree_subtree_add_subtree_sum
  You can see English statement by pressing the LANG button at the top right corner
  You can also use the top tree or the euler tour tree to solve this problem
  My submission

More problems are welcome !