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 !

Thanks, this is pretty neat. It's also pretty interesting how your

`fetch`

method both pulls information from parent and pushes it down to children.You can also do this with the usual down-propagation: just store two "push" variables in each node — one for propagating down the splay tree and another for propagating to your "light" children.

`cancel`

then only makes sense for splay tree roots so maintaining it in`rotate`

is much simpler: just copy parent's value to the child. On the flip side you need to handle the actual "light" children propagation during`expose`

but you're already doing some extra work there because of subtree sum queries.