[Tutorial] Diameter of a tree and its applications

Revision en7, by TheScrasse, 2022-03-16 01:17:14

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. I tried to put a lot of examples to make the understanding easier.
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$$$).

Tree = edges of a diameter + forest

Before describing an algorithm to find a diameter, let's analyze the structure of the tree. Let's assume we've found a diameter $$$a \rightarrow b$$$.

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's consider any component with root $$$d$$$, and one of its nodes $$$c$$$.

We get

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

In other words, the height of each component is at most the distance of the root of the component from an end of the diameter. Of course, this fact is also true for the other end.

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.

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.

Proof

Let's assume that $$$i \rightarrow j$$$ is a diameter, and $$$a \rightarrow b$$$ isn't a diameter. We get $$$\text{dist}(i, a) \geq \text{dist}(i, j)$$$ or $$$\text{dist}(i, b) \geq \text{dist}(i, j)$$$ (because either $$$a$$$ or $$$b$$$ is one of the farthest nodes from $$$i$$$). So, $$$i \rightarrow a$$$ or $$$i \rightarrow b$$$ is a diameter as well. Since $$$a$$$ is one of the farthest nodes from $$$b$$$ (and vice versa),

Counting inversions in $$$O(n \log n)$$$

You can use a Fenwick tree (or a segment tree). There are other solutions (for example, using divide & conquer + merge sort), but they are usually harder to generalize.
For each $$$j$$$, calculate the number of $$$i < j$$$ such that $$$a_i > a_j$$$.
The Fenwick tree should contain the frequency of each value in $$$[1, n]$$$ in the prefix $$$[1, j - 1]$$$ of the array.
So, for each $$$j$$$, the queries look like

  • $$$res := res + \text{range_sum}(a_j + 1, n)$$$
  • add $$$1$$$ in the position $$$a_j$$$ of the Fenwick tree

Observations / slight variations of the problem

By using a Fenwick tree, you are actually calculating the number of inversions for each prefix of the array.

You can calculate the number of swaps required to sort an array (not necessarily a permutation, but for now let's assume that its elements are distinct) by compressing the values of the array. For example, the array $$$[13, 18, 34, 38, 28, 41, 5, 29, 30]$$$ becomes $$$[2, 3, 7, 8, 6, 9, 1, 4, 5]$$$.

You can also calculate the number of swaps required to get an array $$$b$$$ (for now let's assume that its elements are distinct) starting from $$$a$$$, by renaming the values. For example,
$$$a = [2, 3, 7, 8, 6, 9, 1, 4, 5], b = [9, 8, 5, 2, 1, 4, 7, 3, 6]$$$
is equivalent to
$$$a = [4, 8, 7, 2, 9, 1, 5, 6, 3], b = [1, 2, 3, 4, 5, 6, 7, 8, 9]$$$

$$$a^{-1}$$$ (a permutation such that $$$(a^{-1})_{a_x} = x$$$, i.e. $$$(a^{-1})_x$$$ is equal to the position of $$$x$$$ in $$$a$$$) has the same number of inversions as $$$a$$$. For example, $$$[2, 3, 7, 8, 6, 9, 1, 4, 5]$$$ and $$$[7, 1, 2, 8, 9, 5, 3, 4, 6]$$$ have both $$$16$$$ inversions. Sketch of a proof: note that, when you swap two elements in adjacent positions in $$$a$$$, you are swapping two adjacent values in $$$a^{-1}$$$, and the number of inversions in $$$a^{-1}$$$ also increases by $$$1$$$ or decreases by $$$1$$$ (like in Proof 1).

1430E - String Reversal (rating: 1900)

Hint 1
Hint 2
Hint 3
Solution

103148B - Luna Likes Love (EGOI 2021/2)

Hint 1
Hint 2
Hint 3
Hint 4
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

IOI 2019/1
arc120_c (suggested by Ghassane)
Hackerearth — Swapping numbers (Inferno03)
Hackerearth — Make the strings equal (Inferno03)
1526D - Kill Anton (somil_jain_120)
JOI 2021/3 (Final Round) (you can submit here)

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!

Tags ask, ama

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en27 English TheScrasse 2023-07-13 11:15:23 24 Tiny change: 't turned IGM. Now you ' -> 't turned International Grandmaster. Now you '
en26 English 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 English TheScrasse 2022-06-17 15:27:12 12105
en24 English 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 English TheScrasse 2022-03-26 14:07:32 3 Tiny change: 'mple path of $a \right' -> 'mple path $a \right'
en22 English TheScrasse 2022-03-26 14:06:55 173
en21 English TheScrasse 2022-03-26 14:04:27 2448
en20 English TheScrasse 2022-03-26 13:14:16 935
en19 English TheScrasse 2022-03-26 12:53:19 2354
en18 English TheScrasse 2022-03-26 12:25:12 6
en17 English TheScrasse 2022-03-26 12:23:20 1163
en16 English TheScrasse 2022-03-26 11:56:33 1772
en15 English TheScrasse 2022-03-26 11:42:16 779
en14 English TheScrasse 2022-03-26 11:37:47 966 Tiny change: 'e diameter.\n</spoil' -> 'e diameter .\n</spoil'
en13 English TheScrasse 2022-03-25 00:43:26 1585
en12 English TheScrasse 2022-03-25 00:26:04 128
en11 English TheScrasse 2022-03-25 00:22:20 1754
en10 English TheScrasse 2022-03-24 23:45:35 1716 Tiny change: 'ays works.\n\nProof:' -> 'ays works._\n\nProof:'
en9 English TheScrasse 2022-03-24 23:18:42 2333 Reverted to en7
en8 English TheScrasse 2022-03-24 23:17:52 2333 Reverted to en6
en7 English TheScrasse 2022-03-16 01:17:14 2333
en6 English TheScrasse 2022-03-15 00:47:55 330
en5 English 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 English TheScrasse 2022-03-14 23:59:01 19
en3 English TheScrasse 2022-03-14 19:50:27 842
en2 English TheScrasse 2022-03-14 19:05:58 678 Tiny change: ' diameter.\n\n#### P' -> ' diameter._\n\n#### P'
en1 English TheScrasse 2022-03-14 18:47:40 14006 Initial revision (saved to drafts)