3 files changed, 58 insertions, 21 deletions
diff --git a/content/graph/LCA_sparse.cpp b/content/graph/LCA_sparse.cpp
index 221b5ed..3e87cde 100644
--- a/content/graph/LCA_sparse.cpp
+++ b/content/graph/LCA_sparse.cpp
@@ -10,7 +10,7 @@ struct LCA {
 		first.assign(sz(adj), 2 * sz(adj));
 		idx = 0;
 		dfs(adj, root);
-		st.init(&depth);
+		st.init(depth);
 	}
 
 	void dfs(vector<vector<int>>& adj, int v, ll d=0) {
diff --git a/content/graph/binary_lifting.cpp b/content/graph/binary_lifting.cpp
new file mode 100644
index 0000000..0b8c218
--- /dev/null
+++ b/content/graph/binary_lifting.cpp
@@ -0,0 +1,28 @@
+struct Lift {
+	vector<int> dep, par, jmp;
+
+	Lift(vector<vector<int>> &adj, int root):
+			dep(adj.size()), par(adj.size()), jmp(adj.size(), root) {
+		function<void(int,int,int)> dfs = [&](int u, int p, int d) {
+			dep[u] = d, par[u] = p;
+			jmp[u] = dep[p] + dep[jmp[jmp[p]]] == 2*dep[jmp[p]]
+			       ? jmp[jmp[p]] : p;
+			for (int v: adj[u]) if (v != p) dfs(v, u, d+1);
+		};
+		dfs(root, root, 0);
+	}
+
+	int depth(int v) { return dep[v]; }
+	int lift(int v, int d) {
+		while (dep[v] > d) v = dep[jmp[v]] < d ? par[v] : jmp[v];
+		return v;
+	}
+	int lca(int u, int v) {
+		v = lift(v, dep[u]), u = lift(u, dep[v]);
+		while (u != v) {
+			auto &a = jmp[u] == jmp[v] ? par : jmp;
+			u = a[u], v = a[v];
+		}
+		return u;
+	}
+};
diff --git a/content/graph/graph.tex b/content/graph/graph.tex
index 213c597..b38e96e 100644
--- a/content/graph/graph.tex
+++ b/content/graph/graph.tex
@@ -1,12 +1,5 @@
 \section{Graphen}
 
-\begin{algorithm}{Kruskal}
-	\begin{methods}[ll]
-		berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\
-	\end{methods}
-	\sourcecode{graph/kruskal.cpp}
-\end{algorithm}
-
 \begin{algorithm}{Minimale Spannbäume}
 	\paragraph{Schnitteigenschaft}
 	Für jeden Schnitt $C$ im Graphen gilt:
@@ -16,6 +9,12 @@
 	\paragraph{Kreiseigenschaft}
 	Für jeden Kreis $K$ im Graphen gilt:
 	Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
+
+	\subsection{\textsc{Kruskal}}
+	\begin{methods}[ll]
+		berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\
+	\end{methods}
+	\sourcecode{graph/kruskal.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Heavy-Light Decomposition}
@@ -28,7 +27,7 @@
 	\sourcecode{graph/hld.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Lowest Common Ancestor}
+\begin{algorithm}[optional]{Lowest Common Ancestor}
 	\begin{methods}
 		\method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})}
 		\method{getLCA}{findet LCA}{1}
@@ -37,6 +36,17 @@
 	\sourcecode{graph/LCA_sparse.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Binary Lifting}
+	% https://codeforces.com/blog/entry/74847
+	\begin{methods}
+		\method{Lift}{constructor}{\abs{V}}
+		\method{depth}{distance to root of vertex $v$}{1}
+		\method{lift}{vertex above $v$ at depth $d$}{\log(\abs{V})}
+		\method{lca}{lowest common ancestor of $u$ and $v$}{\log(\abs{V})}
+	\end{methods}
+	\sourcecode{graph/binary_lifting.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Centroids}
 	\begin{methods}
 		\method{find\_centroid}{findet alle Centroids des Baums (maximal 2)}{\abs{V}}
@@ -99,7 +109,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/connect.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Erd\H{o}s-Gallai}
+\begin{algorithm}{\textsc{Erd\H{o}s-Gallai}}
 	Sei $d_1 \geq \cdots \geq d_{n}$. Es existiert genau dann ein Graph $G$ mit Degreesequence $d$ falls $\sum\limits_{i=1}^{n} d_i$ gerade ist und für $1\leq k \leq n$: $\sum\limits_{i=1}^{k} d_i \leq k\cdot(k-1)+\sum\limits_{i=k+1}^{n} \min(d_i, k)$
 	\begin{methods}
 		\method{havelHakimi}{findet Graph}{(\abs{V}+\abs{E})\cdot\log(\abs{V})}
@@ -170,7 +180,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
     \sourcecode{graph/virtualTree.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Maximum Cardinatlity Bipartite Matching}
+\begin{algorithm}{Maximum Cardinality Bipartite Matching}
 	\label{kuhn}
 	\begin{methods}
 		\method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})}
@@ -197,7 +207,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 \subsection{Max-Flow}
 
 \optional{
-\subsubsection{Push Relabel}
+\subsubsection{Push Relabel \opthint}
 \begin{methods}
 	\method{maxFlow}{gut bei sehr dicht besetzten Graphen.}{\abs{V}^2\*\sqrt{\abs{E}}}
 	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
@@ -205,24 +215,23 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 \sourcecode{graph/pushRelabel.cpp}
 }
 
+\subsubsection{\textsc{Dinic}'s Algorithm mit Capacity Scaling}
+\begin{methods}
+	\method{maxFlow}{doppelt so schnell wie \textsc{Ford-Fulkerson}}{\abs{V}^2\cdot\abs{E}}
+	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
+\end{methods}
+\sourcecode{graph/dinicScaling.cpp}
+
 \begin{algorithm}{Min-Cost-Max-Flow}
 	\begin{methods}
 		\method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2}
 	\end{methods}
 	\sourcecode{graph/minCostMaxFlow.cpp}
 \end{algorithm}
-\vfill\null
 \columnbreak
 
-\subsubsection{Dinic's Algorithm mit Capacity Scaling}
-\begin{methods}
-	\method{maxFlow}{doppelt so schnell wie Ford Fulkerson}{\abs{V}^2\cdot\abs{E}}
-	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
-\end{methods}
-\sourcecode{graph/dinicScaling.cpp}
-
 \optional{
-\subsubsection{Anwendungen}
+\subsubsection{Anwendungen \opthint}
 \begin{itemize}
 	\item \textbf{Maximum Edge Disjoint Paths}\newline
 	Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen.