From 4ffd5878c78cc0433b718de09a88682a2a99ecfd Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Tue, 31 Oct 2017 22:26:54 +0100
Subject: Adding short paragraph about Centroid Decomposition.

---
 other/other.tex | 7 +++++++
 1 file changed, 7 insertions(+)

(limited to 'other/other.tex')

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}
-- 
cgit v1.2.3

