Trees

Trees have many special properties that make them ubiquitous in competitive programming. Here are a few of those special properties, along with examples of how each can be exploited.

Unique (simple) paths

• tree queries?
• also every edge is a bridge → admits DP

Minimum connectivity

• talk about mahjong

-orientability

An undirected graph is -orientable if it is possible to direct the edges such that each node has an out-degree of at most . This is the class of all pseudo-forests, which also includes trees. For a tree, an easy way to construct such an orientation is to simply direct all edges toward an arbitrary root.

Here’s a problem for which this property is useful:

You are given a tree on nodes, and each node initially has person. For every day , each person can choose to either stay in their current position or move to an adjacent node. Then, nodes will be bombarded, meaning everyone currently on those nodes will die. Find the maximum number of survivors after all days have passed.

You must solve the problem in .

Let’s consider running the process in reverse. It turns out to be equivalent to the following:

1. Initialize all nodes to be white.
2. In step , mark nodes red. Then, for each red node with at least one adjacent white node, mark it white.
3. Repeat 2 for steps.

The final answer is the total number of white nodes.

Let’s refer to the recoloring of any node as a toggle. Note that the total number of toggles is bounded by . Therefore, our goal is to do a constant amount of processing per toggle.

We need to support the following two operations:

1. Toggle a node to red.
2. Simultaneously toggle all red nodes with an adjacent white node to white.

For the second case, note that we can split each toggled red node into two cases:

1. Its parent was white.
2. One of its children was white.

Maintaining the number of white children for each node is easy and only requires time per toggle. For the first type, whenever a node becomes red, we can consider “hooking in” (to use React terminology) to the event that the parent becomes white. Because each node has only one parent, we only need to hook into one event per toggle to red.

Actually, this idea can be generalized to arbitrary graphs. For a -orientable graph, we can apply the same idea to get a final complexity of . In particular, graphs with only edges are -orientable (e.g. by orienting all edges from lower to higher degree), therefore we can always achieve a complexity of .