merge

10 files changed, 239 insertions, 273 deletions

diff --git a/graph/2sat.cpp b/graph/2sat.cpp
index 8fb3d39..75e54e6 100644
--- a/graph/2sat.cpp
+++ b/graph/2sat.cpp
@@ -2,7 +2,7 @@ struct sat2 {
 	int n; // + scc variablen
 	vector<int> sol;
 
-	sat2(int vars) : n(vars*2), adj(vars*2) {};
+	sat2(int vars) : n(vars*2), adj(n) {}
 
 	static int var(int i) {return i << 1;} // use this!
 
@@ -18,20 +18,14 @@ struct sat2 {
 	void addAnd(int a, int b) {addTrue(a); addTrue(b);}
 	void addNand(int a, int b) {addOr(1^a, 1^b);}
 
-	bool solvable() {
+	bool solve() {
 		scc(); //scc code von oben
+		sol.assign(n, -1);
 		for (int i = 0; i < n; i += 2) {
 			if (idx[i] == idx[i + 1]) return false;
+			sol[i] = idx[i] < idx[i + 1];
+			sol[i + 1] = !sol[i];
 		}
 		return true;
 	}
-
-	void assign() {
-		sol.assign(n, -1);
-		for (int i = 0; i < sccCounter; i++) {
-			if (sol[sccs[i][0]] == -1) {
-				for (int v : sccs[i]) {
-					sol[v] = 1;
-					sol[1^v] = 0;
-	}}}}
 };
diff --git a/graph/graph.tex b/graph/graph.tex
index 6fbdb74..060d157 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -1,18 +1,31 @@
 \section{Graphen}
 
-\begin{algorithm}{Eulertouren}
+\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:
+	Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen.
+	($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.)
+	
+	\paragraph{Kreiseigenschaft}
+	Für jeden Kreis $K$ im Graphen gilt:
+	Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
+\end{algorithm}
+
+\begin{algorithm}{Heavy-Light Decomposition}
 	\begin{methods}
-		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
+		\method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})}
 	\end{methods}
-	\sourcecode{graph/euler.cpp}
-	\begin{itemize}
-		\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
-		\item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
-		\item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.}
-		\item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adj} leichter
-		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
-		Die Existenz muss separat geprüft werden.
-	\end{itemize}
+	\textbf{Wichtig:} Intervalle sind halboffen
+	
+	Subbaum unter dem Knoten $v$ ist das Intervall  $[\text{\code{in[v]}},~\text{\code{out[v]}})$.
+	\sourcecode{graph/hld.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Lowest Common Ancestor}
@@ -31,16 +44,20 @@
 	\sourcecode{graph/centroid.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Heavy-Light Decomposition}
+\begin{algorithm}{Eulertouren}
 	\begin{methods}
-		\method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})}
+		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
 	\end{methods}
-	\textbf{Wichtig:} Intervalle sind halboffen
-	
-	Subbaum unter dem Knoten $v$ ist das Intervall  $[\text{\code{in[v]}},~\text{\code{out[v]}})$.
-	\sourcecode{graph/hld.cpp}
+	\sourcecode{graph/euler.cpp}
+	\begin{itemize}
+		\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
+		\item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
+		\item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.}
+		\item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adj} leichter
+		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
+		Die Existenz muss separat geprüft werden.
+	\end{itemize}
 \end{algorithm}
-\clearpage
 
 \begin{algorithm}{Baum-Isomorphie}
 	\begin{methods}
@@ -49,24 +66,6 @@
 	\sourcecode{graph/treeIsomorphism.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Minimale Spannbäume}
-	\paragraph{Schnitteigenschaft}
-	Für jeden Schnitt $C$ im Graphen gilt:
-	Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen.
-	($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.)
-	
-	\paragraph{Kreiseigenschaft}
-	Für jeden Kreis $K$ im Graphen gilt:
-	Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
-\end{algorithm}
-
-\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}
-
 \subsection{Kürzeste Wege}
 
 \subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
@@ -91,6 +90,14 @@ Sei $d_{i\smash{j}}$ die Distanzmatrix von $G$, dann gibt $d_{i\smash{j}}^k$ die
 
 Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} + b_{k\smash{j}}$
 
+\begin{algorithm}{Dynamic Connectivity}
+	\begin{methods}
+		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
+		\method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)}
+		\method{eraseEdge}{entfernt Kante \code{id}}{\log(n)}
+	\end{methods}
+	\sourcecode{graph/connect.cpp}
+\end{algorithm}
 
 \begin{algorithm}{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)$
@@ -100,13 +107,11 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/havelHakimi.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Dynamic Connectivity}
+\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})}
 	\begin{methods}
-		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
-		\method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)}
-		\method{eraseEdge}{entfernt Kante \code{id}}{\log(n)}
+		\method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}}
 	\end{methods}
-	\sourcecode{graph/connect.cpp}
+	\sourcecode{graph/scc.cpp}
 \end{algorithm}
 
 \begin{algorithm}{DFS}
@@ -121,13 +126,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/articulationPoints.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})}
-	\begin{methods}
-		\method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}}
-	\end{methods}
-	\sourcecode{graph/scc.cpp}
-\end{algorithm}
-
 \begin{algorithm}{2-SAT}
 	\sourcecode{graph/2sat.cpp}
 \end{algorithm}
@@ -139,7 +137,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\end{methods}
 	\sourcecode{graph/bronKerbosch.cpp}
 \end{algorithm}
-\clearpage
 
 \begin{algorithm}{Cycle Counting}
 	\begin{methods}
@@ -164,6 +161,14 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/blossom.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Rerooting Template}
+    \sourcecode{graph/reroot.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Virtual Trees}
+    \sourcecode{graph/virtualTree.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Maximal Cardinatlity Bipartite Matching}
 	\label{kuhn}
 	\begin{methods}
@@ -179,13 +184,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/hopcroftKarp.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Maximum Weight Bipartite Matching}
-	\begin{methods}
-		\method{match}{berechnet Matching}{\abs{V}^3}
-	\end{methods}
-	\sourcecode{graph/maxWeightBipartiteMatching.cpp}
-\end{algorithm}
-
 \begin{algorithm}{Global Mincut}
 	\begin{methods}
 		\method{stoer\_wagner}{berechnet globalen Mincut}{\abs{V}\abs{E}+\abs{V}^2\*\log(\abs{E})}
@@ -205,12 +203,21 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 \sourcecode{graph/capacityScaling.cpp}
 }
 
+\optional{
 \subsubsection{Push Relabel}
 \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}
 \end{methods}
-\sourcecode{graph/pushRelabel2.cpp}
+\sourcecode{graph/pushRelabel.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}
 
 \subsubsection{Dinic's Algorithm mit Capacity Scaling}
 \begin{methods}
@@ -218,6 +225,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
 \end{methods}
 \sourcecode{graph/dinicScaling.cpp}
+\vfill*
+\columnbreak
 
 \optional{
 \subsubsection{Anwendungen}
@@ -241,12 +250,15 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 \end{itemize}
 }
 
-\begin{algorithm}{Min-Cost-Max-Flow}
+\begin{algorithm}{Maximum Weight Bipartite Matching}
 	\begin{methods}
-		\method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2}
+		\method{match}{berechnet Matching}{\abs{V}^3}
 	\end{methods}
-	\sourcecode{graph/minCostMaxFlow.cpp}
+	\sourcecode{graph/maxWeightBipartiteMatching.cpp}
 \end{algorithm}
+\vfill*
+\columnbreak
+
 
 \begin{algorithm}[optional]{TSP}
 	\begin{methods}
@@ -261,3 +273,4 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\end{methods}
 	\sourcecode{graph/bitonicTSPsimple.cpp}
 \end{algorithm}
+
diff --git a/graph/havelHakimi.cpp b/graph/havelHakimi.cpp
index 6246fe0..cbd6991 100644
--- a/graph/havelHakimi.cpp
+++ b/graph/havelHakimi.cpp
@@ -1,6 +1,8 @@
 vector<vector<int>> havelHakimi(const vector<int>& deg) {
 	priority_queue<pair<int, int>> pq;
-	for (int i = 0; i < sz(deg); i++) pq.push({deg[i], i});
+	for (int i = 0; i < sz(deg); i++) {
+		if (deg[i] > 0) pq.push({deg[i], i});
+	}
 	vector<vector<int>> adj;
 	while (!pq.empty()) {
 		auto [degV, v] = pq.top(); pq.pop();
diff --git a/graph/maxWeightBipartiteMatching.cpp b/graph/maxWeightBipartiteMatching.cpp
index 5eda19b..a2b0a80 100644
--- a/graph/maxWeightBipartiteMatching.cpp
+++ b/graph/maxWeightBipartiteMatching.cpp
@@ -4,15 +4,14 @@ double costs[N_LEFT][N_RIGHT];
 double match(int l, int r) {
 	vector<double> lx(l), ly(r);
 	//xy is matching from l->r, yx from r->l, or -1
-	vector<int> xy(l, -1), yx(r, -1), augmenting(r);
-	vector<bool> s(l);
+	vector<int> xy(l, -1), yx(r, -1);
 	vector<pair<double, int>> slack(r);
 
 	for (int x = 0; x < l; x++)
 		lx[x] = *max_element(costs[x], costs[x] + r);
 	for (int root = 0; root < l; root++) {
-		augmenting.assign(r, -1);
-		s.assign(l, false);
+		vector<int> aug(r, -1);
+		vector<bool> s(l);
 		s[root] = true;
 		for (int y = 0; y < r; y++) {
 			slack[y] = {lx[root] + ly[y] - costs[root][y], root};
@@ -22,38 +21,30 @@ double match(int l, int r) {
 			double delta = INF;
 			int x = -1;
 			for (int yy = 0; yy < r; yy++) {
-				if (augmenting[yy] < 0) {
-					if (slack[yy].first < delta) {
-						delta = slack[yy].first;
-						x = slack[yy].second;
-						y = yy;
-			}}}
+				if (aug[yy] < 0 && slack[yy].first < delta) {
+					tie(delta, x) = slack[yy];
+					y = yy;
+			}}
 			if (delta > 0) {
 				for (int x = 0; x < l; x++) if (s[x]) lx[x] -= delta;
 				for (int y = 0; y < r; y++) {
-					if (augmenting[y] >= 0) ly[y] += delta;
+					if (aug[y] >= 0) ly[y] += delta;
 					else slack[y].first -= delta;
 			}}
-			augmenting[y] = x;
+			aug[y] = x;
 			x = yx[y];
-			if (x == -1) break;
+			if (x < 0) break;
 			s[x] = true;
 			for (int y = 0; y < r; y++) {
-				if (augmenting[y] < 0) {
+				if (aug[y] < 0) {
 					double alt = lx[x] + ly[y] - costs[x][y];
 					if (slack[y].first > alt) {
 						slack[y] = {alt, x};
 		}}}}
 		while (y >= 0) {
-			// Jede Iteration vergrößert Matching um 1
-			// (können 0-Kanten sein!)
-			int x = augmenting[y];
-			int prec = xy[x];
-			yx[y] = x;
-			xy[x] = y;
-			y = prec;
+			yx[y] = aug[y];
+			swap(y, xy[aug[y]]);
 	}}
-	// Wert des Matchings
 	return accumulate(all(lx), 0.0) +
-	       accumulate(all(ly), 0.0);
+	       accumulate(all(ly), 0.0); // Wert des Matchings
 }
diff --git a/graph/minCostMaxFlow.cpp b/graph/minCostMaxFlow.cpp
index 3526b17..14a222c 100644
--- a/graph/minCostMaxFlow.cpp
+++ b/graph/minCostMaxFlow.cpp
@@ -8,7 +8,6 @@ struct MinCostFlow {
 	vector<vector<int>> adj;
 	vector<int> pref, con;
 	vector<ll> dist;
-
 	const int s, t;
 	ll maxflow, mincost;
 
@@ -27,12 +26,10 @@ struct MinCostFlow {
 		dist.assign(sz(adj), INF);
 		vector<bool> inqueue(sz(adj));
 		queue<int> queue;
-
 		dist[s] = 0;
 		queue.push(s);
 		pref[s] = s;
 		inqueue[s] = true;
-
 		while (!queue.empty()) {
 			int cur = queue.front(); queue.pop();
 			inqueue[cur] = false;
diff --git a/graph/pushRelabel.cpp b/graph/pushRelabel.cpp
index 52ba8b1..904aec6 100644
--- a/graph/pushRelabel.cpp
+++ b/graph/pushRelabel.cpp
@@ -1,109 +1,64 @@
-constexpr ll inf = 1ll<<60;
-
 struct Edge {
-	int from, to;
+	int to, rev;
 	ll f, c;
 };
 
-vector<Edge> edges;
-vector<vector<int>> adj, llist;
-vector<int> height, ccount, que;
-vector<ll> excess;
-vector<list<int>> dlist;
-vector<list<int>::iterator> iter;
-int highest, highestActive;
-
-void addEdge(int from, int to, ll c) {
-	adj[from].push_back(sz(edges));
-	edges.push_back({from, to, 0, c});
-	adj[to].push_back(sz(edges));
-	edges.push_back({to, from, 0, 0});
-}
+vector<vector<Edge>> adj;
+vector<vector<int>> hs;
+vector<ll> ec;
+vector<int> cur, H;
 
-void globalRelabel(int n, int t) {
-	height.assign(n, n);
-	height[t] = 0;
-	ccount.assign(n, 0);
-	que.assign(n+1, 0);
-	int qh = 0, qt = 0;
-	for (que[qt++] = t; qh < qt;) {
-		int v = que[qh++], h = height[v] + 1;
-		for (int id : adj[v]) {
-			if (height[edges[id].to] == n && edges[id ^ 1].c - edges[id ^ 1].f > 0) {
-				ccount[height[edges[id].to] = h]++;
-				que[qt++] = edges[id].to;
-	}}}
-	llist.assign(n+1, {});
-	dlist.assign(n+1, {});
-	for (int v = 0; v < n; v++) {
-		if (height[v] < n) {
-			iter[v] = dlist[height[v]].insert(dlist[height[v]].begin(), v);
-			if (excess[v] > 0) llist[height[v]].push_back(v);
-	}}
-	highest = highestActive = height[que[qt - 1]];
+void addEdge(int u, int v, ll c) {
+    adj[u].push_back({v, (int)sz(adj[v]), 0, c});
+    adj[v].push_back({u, (int)sz(adj[u])-1, 0, 0});
 }
 
-void push(int v, int id) {
-	int u = edges[id].to;
-	ll df = min(excess[v], edges[id].c - edges[id].f);
-	edges[id].f += df;
-	edges[id^1].f -= df;
-	excess[v] -= df;
-	excess[u] += df;
-	if (0 < excess[u] && excess[u] <= df) llist[height[u]].push_back(u);
+void addFlow(Edge& e, ll f) {
+	if (ec[e.to] == 0 && f > 0)
+		hs[H[e.to]].push_back(e.to);
+	e.f += f;
+	adj[e.to][e.rev].f -= f;
+	ec[e.to] += f;
+	ec[adj[e.to][e.rev].to] -= f;
 }
 
-void discharge(int n, int v) {
-	int nh = n;
-	for (int id : adj[v]) {
-		if (edges[id].c - edges[id].f > 0) {
-			if (height[v] == height[edges[id].to] + 1) {
-				push(v, id);
-				if (!excess[v]) return;
-			} else {
-				nh = min(nh, height[edges[id].to] + 1);
-	}}}
-	int h = height[v];
-	if (ccount[h] == 1) {
-		for (int i = h; i <= highest; i++) {
-			for (auto p : dlist[i]) --ccount[height[p]], height[p] = n;
-			dlist[i].clear();
-		}
-		highest = h - 1;
-	} else {
-		--ccount[h], iter[v] = dlist[h].erase(iter[v]), height[v] = nh;
-		if (nh == n) return;
-		++ccount[nh], iter[v] = dlist[nh].insert(dlist[nh].begin(), v);
-		highest = max(highest, highestActive = nh);
-		llist[nh].push_back(v);
-}}
-
 ll maxFlow(int s, int t) {
 	int n = sz(adj);
-	llist.assign(n + 1, {});
-	dlist.assign(n + 1, {});
-	highestActive = highest = 0;
-	height.assign(n, 0);
-	height[s] = n;
-	iter.resize(n);
-	for (int v = 0; v < n; v++) {
-		if (v != s) iter[v] = dlist[height[v]].insert(dlist[height[v]].begin(), v);
-	}
-	ccount.assign(n, 0);
-	ccount[0] = n-1;
-	excess.assign(n, 0);
-	excess[s] = inf;
-	excess[t] = -inf;
-	for (int id : adj[s]) push(s, id);
-	globalRelabel(n, t);
-	while (highestActive >= 0) {
-		if (llist[highestActive].empty()) {
-			highestActive--;
-			continue;
-		}
-		int v = llist[highestActive].back();
-		llist[highestActive].pop_back();
-		discharge(n, v);
-	}
-	return excess[t] + inf;
-}
+	hs.assign(2*n, {});
+	ec.assign(n, 0);
+	cur.assign(n, 0);
+	H.assign(n, 0);
+	H[s] = n;
+	ec[t] = 1;//never set t to active...
+	vector<int> co(2*n);
+	co[0] = n - 1;
+	for (Edge& e : adj[s]) addFlow(e, e.c);
+	for (int hi = 0;;) {
+		while (hs[hi].empty()) if (!hi--) return -ec[s];
+		int v = hs[hi].back();
+		hs[hi].pop_back();
+		while (ec[v] > 0) {
+			if (cur[v] == sz(adj[v])) {
+				H[v] = 2*n;
+				for (int i = 0; i < sz(adj[v]); i++) {
+					Edge& e = adj[v][i];
+					if (e.c - e.f > 0 &&
+					    H[v] > H[e.to] + 1) {
+						H[v] = H[e.to] + 1;
+						cur[v] = i;
+				}}
+				co[H[v]]++;
+				if (!--co[hi] && hi < n) {
+					for (int i = 0; i < n; i++) {
+						if (hi < H[i] && H[i] < n) {
+							co[H[i]]--;
+							H[i] = n + 1;
+				}}}
+				hi = H[v];
+			} else {
+				Edge& e = adj[v][cur[v]];
+				if (e.c - e.f > 0 && H[v] == H[e.to] + 1) {
+					addFlow(adj[v][cur[v]], min(ec[v], e.c - e.f));
+				} else {
+					cur[v]++;
+}}}}}
diff --git a/graph/pushRelabel2.cpp b/graph/pushRelabel2.cpp
deleted file mode 100644
index 7d7defd..0000000
--- a/graph/pushRelabel2.cpp
+++ /dev/null
@@ -1,66 +0,0 @@
-struct Edge {
-	int from, to;
-	ll f, c;
-};
-
-vector<Edge> edges;
-vector<vector<int>> adj, hs;
-vector<ll> ec;
-vector<int> cur, H;
-
-void addEdge(int from, int to, ll c) {
-	adj[from].push_back(sz(edges));
-	edges.push_back({from, to, 0, c});
-	adj[to].push_back(sz(edges));
-	edges.push_back({to, from, 0, 0});
-}
-
-void addFlow(int id, ll f) {
-	if (ec[edges[id].to] == 0 && f > 0)
-		hs[H[edges[id].to]].push_back(edges[id].to);
-	edges[id].f += f;
-	edges[id^1].f -= f;
-	ec[edges[id].to] += f;
-	ec[edges[id].from] -= f;
-}
-
-ll maxFlow(int s, int t) {
-	int n = sz(adj);
-	hs.assign(2*n, {});
-	ec.assign(n, 0);
-	cur.assign(n, 0);
-	H.assign(n, 0);
-	H[s] = n;
-	ec[t] = 1;//never set t to active...
-	vector<int> co(2*n);
-	co[0] = n - 1;
-	for (int id : adj[s]) addFlow(id, edges[id].c);
-	for (int hi = 0;;) {
-		while (hs[hi].empty()) if (!hi--) return -ec[s];
-		int v = hs[hi].back();
-		hs[hi].pop_back();
-		while (ec[v] > 0) {
-			if (cur[v] == sz(adj[v])) {
-				H[v] = 2*n;
-				for (int i = 0; i < sz(adj[v]); i++) {
-					int id = adj[v][i];
-					if (edges[id].c - edges[id].f > 0 &&
-					    H[v] > H[edges[id].to] + 1) {
-						H[v] = H[edges[id].to] + 1;
-						cur[v] = i;
-				}}
-				co[H[v]]++;
-				if (!--co[hi] && hi < n) {
-					for (int i = 0; i < n; i++) {
-						if (hi < H[i] && H[i] < n) {
-							co[H[i]]--;
-							H[i] = n + 1;
-				}}}
-				hi = H[v];
-			} else {
-				auto e = edges[adj[v][cur[v]]];
-				if (e.c - e.f > 0 && H[v] == H[e.to] + 1) {
-					addFlow(adj[v][cur[v]], min(ec[v], e.c - e.f));
-				} else {
-					cur[v]++;
-}}}}}
diff --git a/graph/reroot.cpp b/graph/reroot.cpp
new file mode 100644
index 0000000..4c6a748
--- /dev/null
+++ b/graph/reroot.cpp
@@ -0,0 +1,62 @@
+// Usual Tree DP can be broken down in 4 steps:
+// - Initialize dp[v] = identity
+// - Iterate over all children w and take a value for w 
+//	 by looking at dp[w] and possibly the edge label of v -> w
+// - combine the values of those children
+//	 usually this operation should be commutative and associative
+// - finalize the dp[v] after iterating over all children
+struct Reroot {
+	using T = ll;
+
+	// identity element
+	T E() {}
+	// x: dp value of child
+	// e: index of edge going to child
+	T takeChild(T x, int e) {}
+	T comb(T x, T y) {}
+	// called after combining all dp values of children
+	T fin(T x, int v) {}
+
+	vector<vector<pair<int, int>>> g;
+	vector<int> ord, pae;
+	vector<T> dp;
+
+	T dfs(int v) {
+		ord.push_back(v);
+		for (auto [w, e] : g[v]) {
+			g[w].erase(find(all(g[w]), pair(v, e^1)));
+			pae[w] = e^1;
+			dp[v] = comb(dp[v], takeChild(dfs(w), e));
+		}
+		return dp[v] = fin(dp[v], v);
+	}
+
+	vector<T> solve(int n, vector<pair<int, int>> edges) {
+		g.resize(n);
+		for (int i = 0; i < n-1; i++) {
+			g[edges[i].first].emplace_back(edges[i].second, 2*i);
+			g[edges[i].second].emplace_back(edges[i].first, 2*i+1);
+		}
+		pae.assign(n, -1);
+		dp.assign(n, E());
+		dfs(0);
+		vector<T> updp(n, E()), res(n, E());
+		for (int v : ord) {
+			vector<T> pref(sz(g[v])+1), suff(sz(g[v])+1);
+			if (v != 0) pref[0] = takeChild(updp[v], pae[v]);
+			for (int i = 0; i < sz(g[v]); i++){
+				auto [u, w] = g[v][i];
+				pref[i+1] = suff[i] = takeChild(dp[u], w);
+				pref[i+1] = comb(pref[i], pref[i+1]);
+			}
+			for (int i = sz(g[v])-1; i >= 0; i--) {
+				suff[i] = comb(suff[i], suff[i+1]);
+			}
+			for (int i = 0; i < sz(g[v]); i++) {
+				updp[g[v][i].first] = fin(comb(pref[i], suff[i+1]), v);
+			}
+			res[v] = fin(pref.back(), v);
+		}
+		return res;
+	}
+};
diff --git a/graph/scc.cpp b/graph/scc.cpp
index 1716add..ac9a40b 100644
--- a/graph/scc.cpp
+++ b/graph/scc.cpp
@@ -1,8 +1,7 @@
 vector<vector<int>> adj, sccs;
-int counter, sccCounter;
+int counter;
 vector<bool> inStack;
-// idx enthält den Index der SCC pro Knoten.
-vector<int> low, idx, s;
+vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten.
 
 void visit(int v) {
 	int old = low[v] = counter++;
@@ -15,14 +14,11 @@ void visit(int v) {
 
 	if (old == low[v]) {
 		sccs.push_back({});
-		int u;
-		do {
+		for (int u = -1; u != v;) {
 			u = s.back(); s.pop_back(); inStack[u] = false;
-			idx[u] = sccCounter;
-			sccs[sccCounter].push_back(u);
-		} while (u != v);
-		sccCounter++;
-}}
+			idx[u] = sz(sccs) - 1;
+			sccs.back().push_back(u);
+}}}
 
 void scc() {
 	inStack.assign(sz(adj), false);
@@ -30,7 +26,7 @@ void scc() {
 	idx.assign(sz(adj), -1);
 	sccs.clear();
 
-	counter = sccCounter = 0;
+	counter = 0;
 	for (int i = 0; i < sz(adj); i++) {
 		if (low[i] < 0) visit(i);
 }}
diff --git a/graph/virtualTree.cpp b/graph/virtualTree.cpp
new file mode 100644
index 0000000..2fcea80
--- /dev/null
+++ b/graph/virtualTree.cpp
@@ -0,0 +1,22 @@
+// needs dfs in- and out- time and lca function
+vector<int> in, out;
+
+void virtualTree(vector<int> ind) { // indices of used nodes
+	sort(all(ind), [&](int x, int y) {return in[x] < in[y];});
+	for (int i=0; i<sz(a)-1; i++) {
+		ind.push_back(lca(ind[i], ind[i+1]));
+	}
+	sort(all(ind), [&](int x, int y) {return in[x] < in[y];});
+	ind.erase(unique(all(ind)), ind.end());
+
+	int n = ind.size();
+	vector<vector<int>> tree(n);
+	vector<int> st = {0};
+	for (int i=1; i<n; i++) {
+		while (in[ind[i]] >= out[ind[st.back()]]) st.pop_back();
+		tree[st.back()].push_back(i);
+		st.push(i);
+	}
+	// virtual directed tree with n nodes, original indices in ind
+	// weights can be calculated, e.g. with binary lifting
+}