[Tutorial] Diameter of a tree and its applications

Правка en18, от TheScrasse, 2022-03-26 12:25:12

Hello everyone,
finding the diameter is one of the most frequent ways to solve problems about trees. In this tutorial we will see how to find a diameter and some of its properties, and we will use them to solve some problems of increasing difficulty.
The first part of the tutorial is quite basic, so feel free to skip it and jump to the problems if you already know the concepts.

Target: rating $$$[1400, 2100]$$$ on CF
Prerequisites: basic graph theory, greedy

The diameter

Given an unweighted tree, let's define $$$\text{dist}(a, b) =$$$ the number of edges in the simple path $$$a \rightarrow b$$$.

A diameter of the tree is a simple path $$$a \rightarrow b$$$ that maximizes $$$\text{dist}(a, b)$$$ over all pairs of nodes. If there are multiple diameters, let's pick any of them.

The same definition is valid for a weighted tree with nonnegative weights (with $$$\text{dist}(a, b) =$$$ the sum of the weights of the edges in the simple path $$$a \rightarrow b$$$).

Finding a diameter

Given a tree with $$$n$$$ nodes are multiple ways to find a diameter. Here is one of the simplest ways:

Run a DFS from any node $$$p$$$. Let $$$a$$$ be a node whose distance from node $$$p$$$ is maximized. Run another DFS from node $$$a$$$. Let $$$b$$$ be a node whose distance from node $$$a$$$ is maximized. $$$a \rightarrow b$$$ is a diameter.

Tree = edges of a diameter + forest

Before proving the previous algorithm, let's analyze the structure of the tree (we will mention the diameter, but we will not use the fact that $$$a \rightarrow b$$$ is actually a diameter before proving it).

We started a DFS from node $$$p = 16$$$, and we got that node $$$a = 1$$$ is the farthest from $$$p$$$, and node $$$b = 7$$$ is the farthest from $$$a$$$.

Let's represent the diameter on a line. If you remove the edges of the diameter, you get a forest (i.e., several trees). Let's root each tree at the node in the diameter. What's the height (i.e., the maximum distance from the root to any node) of each component?

Let $$$q$$$ be the root of the component of $$$p$$$. Let's consider any component whose root $$$d$$$ is between $$$a$$$ (included) and $$$q$$$ (excluded), and one of its nodes $$$c$$$.

We get

$$$\text{dist}(p, a) \geq \text{dist}(p, c) \implies \text{dist}(p, a) - \text{dist}(p, d) \geq \text{dist}(p, c) - \text{dist}(p, d) \implies \text{dist}(a, d) \geq \text{dist}(c, d)$$$.

In other words, the height of each component with root in the left half of the diameter (i.e., $$$\text{dist}(a, d) < \text{dist}(d, b)$$$) is at most the distance of the root of the component from the left end of the diameter.

You can prove the same statement for the right half of the diameter (i.e., $$$\text{dist}(a, d) \geq \text{dist}(d, b)$$$), using that $$$b$$$ is the farthest node from $$$a$$$.

Farthest node for each node

For each node $$$i$$$, let's find a node $$$j$$$ such that $$$\text{dist}(i, j)$$$ is maximum.

Claim: $$$j = a$$$ or $$$j = b$$$ always works.

Proof:

  • If $$$j = j_1$$$ works ($$$j_1$$$ is not in the same component of $$$i$$$; let's assume without loss of generality that $$$j_1$$$ is closer to $$$a$$$ than to $$$b$$$), $$$\text{dist}(i, j_1) = \text{dist}(i, r) + \text{dist}(r, j_1) \leq \text{dist}(i, r) + \text{dist}(r, a) = \text{dist}(i, a)$$$. Then, $$$j = a$$$ also works.
  • If $$$j = j_2$$$ works ($$$j_2$$$ is in the same component of $$$i$$$), $$$\text{dist}(i, j_1) \leq \text{dist}(i, r) + \text{dist}(r, j_1) \leq \text{dist}(i, r) + \text{dist}(r, a) = \text{dist}(i, a)$$$. Then, $$$j = a$$$ also works.

Proof that $$$a \rightarrow b$$$ is a diameter

Now we can finish the proof.

Suppose that $$$u \rightarrow v$$$ is a diameter. We have either $$$\text{dist}(u, a) \geq \text{dist}(u, v)$$$ or $$$\text{dist}(u, b) \geq \text{dist}(u, v)$$$ (see "Farthest node for each node").

Let's assume without loss of generality that $$$\text{dist}(u, b) \geq \text{dist}(u, v)$$$. We get $$$\text{dist}(a, b) \geq \text{dist}(u, b) \geq \text{dist}(u, v)$$$, so $$$a \rightarrow b$$$ is a diameter.

Observations

The algorithm also works in a weighted tree with positive edges (we've never used that the weights are $$$1$$$).

However, it doesn't work on general graphs (discussion).

How to use the diameter

Most of the times, spamming "the farthest node from each node is one end of the diameter" and "the height of each component is smaller than the distance to the closest end of the diameter" is enough to reduce the problem to something simpler.

You may need to consider any path of the tree. Find a diameter $$$a \rightarrow b$$$. There are two cases: the path intersects (blue) or doesn't intersect (green) the diameter.

Then, you may wonder how to make the path longer / "more optimal" / etc. according to the statement. For example, you may need to use $$$\text{dist}(7, 5) \geq \text{dist}(5, 19)$$$ to show that $$$8 \rightarrow 7$$$ is "more optimal" than $$$8 \rightarrow 19$$$.

1004E - Sonya and Ice Cream (rating: 2400)

Hint 1
Hint 2
Hint 3
Solution

633F - The Chocolate Spree (rating: 2600)

Hint 1
Hint 2
Hint 3
Solution

arc088_e (rating: 2231)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

arc097_e (rating: 2247)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

Other problems

102694B - Dynamic Diameter
abc221_f

Conclusions

We've seen that a lot of problems where you have to swap adjacent elements can be tackled with greedy observations, such as looking at the optimal relative positions of the values in the final array; then, a lot of these problems can be reduced to "find the number of inversions" or similar.

Of course, suggestions/corrections are welcome. In particular, please share in the comments other problems where you have to swap adjacent elements.

I hope you enjoyed the blog!

Теги ask, ama

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en27 Английский TheScrasse 2023-07-13 11:15:23 24 Tiny change: 't turned IGM. Now you ' -> 't turned International Grandmaster. Now you '
en26 Английский TheScrasse 2023-07-12 22:32:10 91 Tiny change: 'Old blog' -> 'I've just turned IGM. Now you can ask me anything in the comments.' (published)
en25 Английский TheScrasse 2022-06-17 15:27:12 12105
en24 Английский TheScrasse 2022-03-26 14:49:37 24 Tiny change: 'u have to swap adjacent elements.\n\nI hop' -> 'u have to use the diameter.\n\nI hop'
en23 Английский TheScrasse 2022-03-26 14:07:32 3 Tiny change: 'mple path of $a \right' -> 'mple path $a \right'
en22 Английский TheScrasse 2022-03-26 14:06:55 173
en21 Английский TheScrasse 2022-03-26 14:04:27 2448
en20 Английский TheScrasse 2022-03-26 13:14:16 935
en19 Английский TheScrasse 2022-03-26 12:53:19 2354
en18 Английский TheScrasse 2022-03-26 12:25:12 6
en17 Английский TheScrasse 2022-03-26 12:23:20 1163
en16 Английский TheScrasse 2022-03-26 11:56:33 1772
en15 Английский TheScrasse 2022-03-26 11:42:16 779
en14 Английский TheScrasse 2022-03-26 11:37:47 966 Tiny change: 'e diameter.\n</spoil' -> 'e diameter .\n</spoil'
en13 Английский TheScrasse 2022-03-25 00:43:26 1585
en12 Английский TheScrasse 2022-03-25 00:26:04 128
en11 Английский TheScrasse 2022-03-25 00:22:20 1754
en10 Английский TheScrasse 2022-03-24 23:45:35 1716 Tiny change: 'ays works.\n\nProof:' -> 'ays works._\n\nProof:'
en9 Английский TheScrasse 2022-03-24 23:18:42 2333 Reverted to en7
en8 Английский TheScrasse 2022-03-24 23:17:52 2333 Reverted to en6
en7 Английский TheScrasse 2022-03-16 01:17:14 2333
en6 Английский TheScrasse 2022-03-15 00:47:55 330
en5 Английский TheScrasse 2022-03-15 00:29:55 1145 Tiny change: 'eter).\n\n\n\n#### P' -> 'eter).\n\n![ ](https://i.imgur.com/45DIau0.png)\n\n#### P'
en4 Английский TheScrasse 2022-03-14 23:59:01 19
en3 Английский TheScrasse 2022-03-14 19:50:27 842
en2 Английский TheScrasse 2022-03-14 19:05:58 678 Tiny change: ' diameter.\n\n#### P' -> ' diameter._\n\n#### P'
en1 Английский TheScrasse 2022-03-14 18:47:40 14006 Initial revision (saved to drafts)