Adding short paragraph about Centroid Decomposition.

2 files changed, 7 insertions, 0 deletions

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
--- a/tcr.pdf
+++ b/tcr.pdf