From 4ffd5878c78cc0433b718de09a88682a2a99ecfd Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Tue, 31 Oct 2017 22:26:54 +0100 Subject: Adding short paragraph about Centroid Decomposition. --- other/other.tex | 7 +++++++ tcr.pdf | Bin 297676 -> 298283 bytes 2 files changed, 7 insertions(+) diff --git a/other/other.tex b/other/other.tex index 012d100..dcad30b 100644 --- a/other/other.tex +++ b/other/other.tex @@ -135,6 +135,13 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen. Beantworte Queries offline durch schrittweise Vergrößern/Verkleinern des aktuellen Intervalls. Laufzeit:~$\mathcal{O}(n\cdot\sqrt{n})$. (Anzahl der Blöcke als Konstante in Code schreiben.) + + \item \textbf{Centroids of a Tree:} + Ein \emph{Centroid} ist ein Konten, der einen Baum in Komponenten der maximalen Größe $\frac{\vert V \vert}{2}$ splitted. + Es kann $2$ Centroids geben! + \textbf{Centroid Decomposition:} + Wähle zufälligen Knoten und mache DFS. + Verschiebe ausgewählten Knoten in Richtung des tiefsten Teilbaums, bis Centroid gefunden. Entferne Knoten, mache rekursiv in Teilbäumen weiter. Laufzeit:~$\mathcal{O}(\vert V \vert \log(\vert V \vert))$. \end{itemize} \subsection{Tipps \& Tricks} diff --git a/tcr.pdf b/tcr.pdf index 060daa7..fe42202 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3