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

→ Pay attention

Before contest
XIX Open Olympiad in Informatics - Final Stage, Day 1 (Unrated, Online Mirror, IOI rules)
19:52:48
Register now »

→ Streams

Blitz Cup R2 vs jonathanirvings

By Egor

Before stream 02:42:48

Blitz Cup 2025: jonathanirvings vs Egor (R2)

By jonathanirvings

Before stream 02:47:48

Codeforces Blitz Cup 2025: golomb vs tourist (R2)

By tourist

Before stream 05:47:48

And 1 more running

View all →

→ Top rated

#	User	Rating
1	tourist	3857
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3463
9	ecnerwala	3451
10	heuristica	3431

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	165
2	-is-this-fft-	161
3	Qingyu	160
4	Dominater069	158
5	atcoder_official	157
6	adamant	155
7	Um_nik	151
8	djm03178	150
8	luogu_official	150
10	awoo	148

View all →

→ Find user

→ Recent actions

Detailed →

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

Revision en2, by Aveiro_quanyue, 2023-03-28 13:52:36

Nowcoder problem (Chinese) link

English version

First I would like to thank ShaoNianTongXue5307 for his idea!

centroid decomposition

History

Revisions

Rev.	By	When	Δ	Comment
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\nP' -> 'troid is $B$. \n\nP'
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)