Hybrid Tutorial #-1: Heavy-Light Decomposition
Автор: Colin Galen
Загружено: 2020-08-11
Просмотров: 18847
Link to blog: https://codeforces.com/blog/entry/81317
Legend for colors of things I draw on the tree (it also shows up later in the video):
Purple - subtree size
Orange - vertex depth
Brown - vertex label
Blue - top of the chain containing a vertex
Intro 00:00
Problem statement 01:20
Prerequisites 05:05
Heavy/light edges (concept) 07:50
Properties of heavy edges (concept) 09:50
Proof of time complexity (concept) 13:31
Finding heavy/light edges (implementation) 20:20
Labelling vertices (implementation) 24:10
Finding tops of chains (implementation) 25:48
Evaluating queries (implementation) 28:37
Evaluating vertical chains (implementation) 29:57
Edge queries (implementation) 37:13
Доступные форматы для скачивания:
Скачать видео mp4
-
Информация по загрузке:
