A note on a nowcoder problem -- Centroid decomposition (点分治)

Revision en34, by Aveiro_quanyue, 2023-03-28 15:02:29

Nowcoder problem (Chinese) link

English version

First I would like to thank ShaoNianTongXue5307 for his idea!

This is a learning note, most for myself. Most of this blog is not original.

Part 1: Problem Statement:

A tree $$$T=(V, E)$$$ has $$$n$$$ vertices and $$$n-1$$$ edges, the weight of each vertex $$$i$$$ is $$$a_i$$$.

For each edge $$$e$$$, you can determine its direction, i.e., for two vertices $$$u, v$$$, there are two states: $$$u \rightarrow v$$$ and $$$v \rightarrow u$$$. There are $$$2^{n-1}$$$ states in total.

For each state $$$S$$$, we define $$$f(S)$$$ as

$$$f(S) := \sum\limits_{(u, v) \in V \times V, v\,\text{is reachable from}\,u} |a_u - a_v|$$$.

Compute the sum of $$$f(S)$$$ over all $$$2^{n-1}$$$ states $$$S$$$, modulo $$$998244353$$$.

Example:

Suppose $$$n=3$$$, and two edges connect $$$(1, 2), (2, 3)$$$, respectively. $$$a_1 = 3, a_2 = 1, a_3 = 2$$$, the answer is $$$14$$$.

Constraints: $$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq a_i \leq 10^9$$$.

Part 2: What is the centroid decomposition good at?

Before we learn centroid decomposition, we should first know what it is good at. For a tree $$$T = (V, E)$$$, we can decompose $$$V$$$ into $$$V = V_1 \cup V_2 \cup ... \cup V_t$$$, where $$$V_i (1 \leq i \leq t)$$$ are pairwise disjoint non-empty sets. $$$V_1$$$ is a singleton which contains only one element: The centroid. $$$V_2, ..., V_t$$$ are the connected components of $$$T \setminus V_1$$$. We want to calculate some function $$$f(T)$$$, and we assume that the base case, where $$$V(T) = 1$$$, is easy to calculate. This assumption is not strict, because if we can't even deal with the case where $$$V(T)=1$$$, we can actually achieve nothing. The another important function besides $$$f$$$ is the merge function: $$$merge(V_1, V_2, ..., V_t)$$$. Formally

$$$f(V) = \sum\limits_{i=1}^t f(V_i) + merge(V_1, V_2, ..., V_t)$$$. (1)

Like the merge sort, the number of iterations in the centroid decomposition algorithm is $$$O(log |V|)$$$, so it takes roughly $$$O(log |V| \cdot merge)$$$ times. Therefore, the most important advantage to use centroid decomposition is that the merge function could be computed fast enough. Otherwise, it is even slower than the brute force! In our solution merge is $$$O(|V|log|V|)$$$ so its complexity is $$$O(|V|log^2|V|)$$$.

Part 3: What is a centroid, and what is a centroid decomposition?

For a tree, the vertex $$$v$$$ is called a centroid if and only if for any subtree rooted at v’s child has a size at most half the size of the original tree rooted at $$$v$$$. For example, the centroids for the path A--B--C--D are B and C.

Property $$$1$$$: A tree has one or two centroids.

Proof: First, we prove that one tree has at least one centroid. The centroid could be found using a constructive algorithm. First we specify an original root $$$r$$$. Initialize $$$v$$$ as $$$r$$$. Check whether $$$v$$$ is a centroid. If yes, we have already done. If not, replace $$$v$$$ with $$$v$$$'s heavy child $$$u$$$, i.e., $$$argmax(u)\{size[u] \mid u\,\text{is}\,v\text{'s child}\}$$$. The iteration will terminate since the size if finite. When it terminates, the size of subtrees rooted at $$$v$$$'s children $$$\leq \frac{|V|}{2}$$$. We need to be careful that, when the tree is rooted at $$$v$$$ (instead of $$$r$$$), the parent of $$$v$$$ in the $$$r$$$-rooted tree becomes a child of $$$v$$$ in the $$$v$$$-rooted tree, so we need to check the parent of $$$v$$$ in the $$$r$$$-rooted tree. Since the algorithm does not terminate at $$$v$$$'s parent, the size of $$$v \leq \frac{|V|}{2}$$$, therefore, (the size of $$$v$$$'s parent) — (the size of $$$v$$$'s parent) $$$\leq \frac{|V|}{2}$$$, which also satisfies the condition.

Second, we prove that one tree has at most two centroids. Suppose $$$a$$$ and $$$b$$$ are two centroids. Then, there is a subtree of $$$a$$$'s child ($$$A$$$) containing $$$b$$$, and a subtree of $$$b$$$'s child ($$$B$$$) containing $$$a$$$, $$$A \cup B = V, |A|, |B| \leq \frac{|V|}{2}$$$. By the principle of inclusion-exclusion (PIE), $$$A$$$ and $$$B$$$ must be disjoint, therefore there is an edge $$$ab$$$. So there cannot be $$$\geq 3$$$ centroids, and if it contains $$$2$$$ centroids, these two centroids must be adjacent.

Property $$$2$$$: $$$v := argmin(v)\{max\{size[u] \mid u\,\text{is}\,v\text{'s child in the tree rooted at }v\}\}$$$ is a centroid. This can be proved using the fact that every tree has at least one centroid, so the "best" vertex must be a centroid. In English, for a vertex $$$v$$$, lets the score of $$$v$$$ be the maximum size of subtrees rooted at $$$v$$$'s children. The $$$v$$$ with the minimum score is the centroid.

Property $$$3$$$: $$$v$$$ is a centroid if and only if for arbitrary $$$q \in V$$$, $$$\sum\limits_{u \in V} d(u, v) \leq \sum\limits_{u \in V} d(u, q)$$$.

Proof: $$$rightarrow$$$:

Tags centroid decomposition

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en80 English Aveiro_quanyue 2023-03-30 12:21:13 2 Tiny change: 'the size if finite. W' -> 'the size is finite. W'
en79 English Aveiro_quanyue 2023-03-29 05:20:01 4
en78 English Aveiro_quanyue 2023-03-29 05:17:51 8 Tiny change: 'ssions/40126314). I paste' -> 'ssions/40135200). I paste'
en77 English Aveiro_quanyue 2023-03-29 05:16:17 115
en76 English Aveiro_quanyue 2023-03-28 18:38:23 9 Tiny change: 'ize of $v$'s parent) $\leq \f' -> 'ize of $v$) $\leq \f'
en75 English Aveiro_quanyue 2023-03-28 18:36:00 2
en74 English Aveiro_quanyue 2023-03-28 17:57:37 1 Tiny change: 'rge)$ times. Therefor' -> 'rge)$ time. Therefor'
en73 English Aveiro_quanyue 2023-03-28 17:25:18 2 Tiny change: 'diameter mast pass th' -> 'diameter must pass th'
en72 English Aveiro_quanyue 2023-03-28 17:15:24 22
en71 English Aveiro_quanyue 2023-03-28 17:11:42 0 (published)
en70 English Aveiro_quanyue 2023-03-28 17:11:16 265
en69 English Aveiro_quanyue 2023-03-28 16:51:11 92
en68 English Aveiro_quanyue 2023-03-28 16:48:54 71
en67 English Aveiro_quanyue 2023-03-28 16:45:07 420
en66 English Aveiro_quanyue 2023-03-28 16:41:28 170
en65 English Aveiro_quanyue 2023-03-28 16:38:27 8 Tiny change: 'fast. Code:\n\n<spoi' -> 'fast. Code (645ms):\n\n<spoi'
en64 English Aveiro_quanyue 2023-03-28 16:37:38 215
en63 English Aveiro_quanyue 2023-03-28 16:35:57 2 Tiny change: 'rite the `Merge` func' -> 'rite the `merge` func'
en62 English Aveiro_quanyue 2023-03-28 16:35:21 187
en61 English Aveiro_quanyue 2023-03-28 16:33:58 6386
en60 English Aveiro_quanyue 2023-03-28 16:30:19 49
en59 English Aveiro_quanyue 2023-03-28 16:28:18 321
en58 English Aveiro_quanyue 2023-03-28 16:24:56 116
en57 English Aveiro_quanyue 2023-03-28 16:22:03 433
en56 English Aveiro_quanyue 2023-03-28 16:19:10 222
en55 English Aveiro_quanyue 2023-03-28 16:16:52 87
en54 English Aveiro_quanyue 2023-03-28 16:15:18 136
en53 English Aveiro_quanyue 2023-03-28 16:14:15 2 Tiny change: 'troid is $C$. \n\n**P' -> 'troid is $B$. \n\n**P'
en52 English Aveiro_quanyue 2023-03-28 16:13:49 115
en51 English Aveiro_quanyue 2023-03-28 16:12:48 36
en50 English Aveiro_quanyue 2023-03-28 16:12:23 211
en49 English Aveiro_quanyue 2023-03-28 16:09:47 6 Tiny change: ' \nIt can pass [ABC291EX' -> ' \nIt can AC [ABC291EX'
en48 English Aveiro_quanyue 2023-03-28 16:09:16 119
en47 English Aveiro_quanyue 2023-03-28 16:07:51 662
en46 English Aveiro_quanyue 2023-03-28 15:53:38 240
en45 English Aveiro_quanyue 2023-03-28 15:51:38 266
en44 English Aveiro_quanyue 2023-03-28 15:48:44 1865
en43 English Aveiro_quanyue 2023-03-28 15:45:58 32 Tiny change: '8412.html).' -> '8412.html) by [user:lingfunny]. '
en42 English Aveiro_quanyue 2023-03-28 15:45:09 198
en41 English Aveiro_quanyue 2023-03-28 15:37:36 145
en40 English Aveiro_quanyue 2023-03-28 15:32:34 23 Tiny change: 's children. The $v$ ' -> 's children in the $v$-rooted tree. The $v$ '
en39 English Aveiro_quanyue 2023-03-28 15:28:02 336
en38 English Aveiro_quanyue 2023-03-28 15:22:07 537
en37 English Aveiro_quanyue 2023-03-28 15:13:59 258
en36 English Aveiro_quanyue 2023-03-28 15:10:53 184
en35 English Aveiro_quanyue 2023-03-28 15:09:23 316
en34 English Aveiro_quanyue 2023-03-28 15:02:29 49
en33 English Aveiro_quanyue 2023-03-28 14:56:27 4 Tiny change: ' \in V} d(q, v)$.\n\n\n\' -> ' \in V} d(u, q)$.\n\n\n\'
en32 English Aveiro_quanyue 2023-03-28 14:56:13 81
en31 English Aveiro_quanyue 2023-03-28 14:48:03 2 Tiny change: 'ooted at }$v$\\}\\}$ is' -> 'ooted at }v\\}\\}$ is'
en30 English Aveiro_quanyue 2023-03-28 14:47:43 26 Tiny change: 't{'s child}\\}\\}$ is' -> 't{'s child in the tree rooted at }$v$\\}\\}$ is'
en29 English Aveiro_quanyue 2023-03-28 14:46:13 68
en28 English Aveiro_quanyue 2023-03-28 14:45:08 157
en27 English Aveiro_quanyue 2023-03-28 14:42:46 229
en26 English Aveiro_quanyue 2023-03-28 14:41:19 155
en25 English Aveiro_quanyue 2023-03-28 14:38:36 139
en24 English Aveiro_quanyue 2023-03-28 14:36:52 46
en23 English Aveiro_quanyue 2023-03-28 14:35:28 1 Tiny change: 'x\\{\\}\\}. \n\n\n\n' -> 'x\\{\\}\\}$. \n\n\n\n'
en22 English Aveiro_quanyue 2023-03-28 14:35:14 198
en21 English Aveiro_quanyue 2023-03-28 14:31:23 593
en20 English Aveiro_quanyue 2023-03-28 14:27:34 70
en19 English Aveiro_quanyue 2023-03-28 14:26:38 12 Tiny change: '\\{size[u]|u \text{is} v\text{'s c' -> '\\{size[u] \midu\,\text{is} v\,\text{'s c'
en18 English Aveiro_quanyue 2023-03-28 14:26:14 5 Tiny change: 'eavy child, i.e., $arg\max\\{size' -> 'eavy child $u$, i.e., $argmax\\{size'
en17 English Aveiro_quanyue 2023-03-28 14:25:51 2 Tiny change: 'd, i.e., $\argmax\\{size' -> 'd, i.e., $arg\max\\{size'
en16 English Aveiro_quanyue 2023-03-28 14:25:38 297
en15 English Aveiro_quanyue 2023-03-28 14:19:50 180
en14 English Aveiro_quanyue 2023-03-28 14:15:27 65
en13 English Aveiro_quanyue 2023-03-28 14:13:32 260
en12 English Aveiro_quanyue 2023-03-28 14:11:01 81
en11 English Aveiro_quanyue 2023-03-28 14:10:09 234
en10 English Aveiro_quanyue 2023-03-28 14:08:54 40
en9 English Aveiro_quanyue 2023-03-28 14:08:01 22
en8 English Aveiro_quanyue 2023-03-28 14:07:29 176
en7 English Aveiro_quanyue 2023-03-28 14:05:35 128
en6 English Aveiro_quanyue 2023-03-28 14:04:08 153
en5 English Aveiro_quanyue 2023-03-28 14:02:13 453
en4 English Aveiro_quanyue 2023-03-28 13:57:57 320
en3 English Aveiro_quanyue 2023-03-28 13:53:13 869
en2 English Aveiro_quanyue 2023-03-28 13:52:36 32
en1 English Aveiro_quanyue 2023-03-28 13:51:56 258 Initial revision (saved to drafts)