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

Правка en10, от Aveiro_quanyue, 2023-03-28 14:08:54

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)$$$.

Like the merge sort, the number of iterations in the centroid decomposition algorithm is $$$O(log |V|)$$$

Теги centroid decomposition

История

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