merge mzuenni changes

9 files changed, 121 insertions, 74 deletions

diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp
index 6470232..eee5082 100644
--- a/content/graph/bitonicTSP.cpp
+++ b/content/graph/bitonicTSP.cpp
@@ -27,5 +27,5 @@ auto bitonicTSP() {
 	(lt.back() == 1 ? lt : ut).push_back(0);
 	reverse(all(lt));
 	lt.insert(lt.end(), all(ut));
-	return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+	return lt; // Enthält Knoten 0 zweimal. An erster und letzter Position.
 }
diff --git a/content/graph/bitonicTSPsimple.cpp b/content/graph/bitonicTSPsimple.cpp
index 8b6e6c5..cacfb9c 100644
--- a/content/graph/bitonicTSPsimple.cpp
+++ b/content/graph/bitonicTSPsimple.cpp
@@ -23,5 +23,5 @@ auto bitonicTSP() {
 			rl.push_back(v); p2 = v;
 	}}
 	lr.insert(lr.end(), rl.rbegin(), rl.rend());
-	return lr;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+	return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position.
 }
diff --git a/content/graph/connect.cpp b/content/graph/connect.cpp
index ffcd6c2..7940b37 100644
--- a/content/graph/connect.cpp
+++ b/content/graph/connect.cpp
@@ -10,7 +10,7 @@ struct connect {
 	}
 
 	void addEdge(int u, int v, int id) {
-		lct.nodes[id + n] = LCT::Node(id + n, id + n);
+		lct.nodes[id + n] = LCT::Node(id + n, id);
 		edges[id] = {u, v};
 		if (connected(u, v)) {
 			int old = lct.query(&lct.nodes[u], &lct.nodes[v]);
diff --git a/content/graph/dinic.cpp b/content/graph/dinic.cpp
new file mode 100644
index 0000000..2e58a2d
--- /dev/null
+++ b/content/graph/dinic.cpp
@@ -0,0 +1,55 @@
+struct Edge {
+	int to, rev;
+	ll f, c;
+};
+
+vector<vector<Edge>> adj;
+int s, t;
+vector<int> pt, dist;
+
+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});
+}
+
+bool bfs() {
+	dist.assign(sz(adj), -1);
+	dist[s] = 0;
+	queue<int> q({s});
+	while (!q.empty() && dist[t] < 0) {
+		int v = q.front(); q.pop();
+		for (Edge& e : adj[v]) {
+			if (dist[e.to] < 0 && e.c - e.f > 0) {
+				dist[e.to] = dist[v] + 1;
+				q.push(e.to);
+	}}}
+	return dist[t] >= 0;
+}
+
+ll dfs(int v, ll flow = INF) {
+	if (v == t || flow == 0) return flow;
+	for (; pt[v] < sz(adj[v]); pt[v]++) {
+		Edge& e = adj[v][pt[v]];
+		if (dist[e.to] != dist[v] + 1) continue;
+		ll cur = dfs(e.to, min(e.c - e.f, flow));
+		if (cur > 0) {
+			e.f += cur;
+			adj[e.to][e.rev].f -= cur;
+			return cur;
+	}}
+	return 0;
+}
+
+ll maxFlow(int source, int target) {
+	s = source, t = target;
+	ll flow = 0;
+	while (bfs()) {
+		pt.assign(sz(adj), 0);
+		ll cur;
+		do {
+			cur = dfs(s);
+			flow += cur;
+		} while (cur > 0);
+	}
+	return flow;
+}
diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp
index f4e833a..0974b78 100644
--- a/content/graph/dinicScaling.cpp
+++ b/content/graph/dinicScaling.cpp
@@ -26,17 +26,18 @@ bool bfs(ll lim) {
 	return dist[t] >= 0;
 }
 
-bool dfs(int v, ll flow) {
-	if (v == t) return true;
+ll dfs(int v, ll flow) {
+	if (v == t || flow == 0) return flow;
 	for (; pt[v] < sz(adj[v]); pt[v]++) {
 		Edge& e = adj[v][pt[v]];
 		if (dist[e.to] != dist[v] + 1) continue;
-		if (e.c - e.f >= flow && dfs(e.to, flow)) {
-			e.f += flow;
-			adj[e.to][e.rev].f -= flow;
-			return true;
+		ll cur = dfs(e.to, min(e.c - e.f, flow));
+		if (cur > 0) {
+			e.f += cur;
+			adj[e.to][e.rev].f -= cur;
+			return cur;
 	}}
-	return false;
+	return 0;
 }
 
 ll maxFlow(int source, int target) {
@@ -45,7 +46,11 @@ ll maxFlow(int source, int target) {
 	for (ll lim = (1LL << 62); lim >= 1; lim /= 2) {
 		while (bfs(lim)) {
 			pt.assign(sz(adj), 0);
-			while (dfs(s, lim)) flow += lim;
+			ll cur;
+			do {
+				cur = dfs(s, lim);
+				flow += cur;
+			} while (cur > 0);
 	}}
 	return flow;
 }
diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp
index 73a9eae..ec36026 100644
--- a/content/graph/pushRelabel.cpp
+++ b/content/graph/pushRelabel.cpp
@@ -29,7 +29,7 @@ ll maxFlow(int s, int t) {
 	cur.assign(n, 0);
 	H.assign(n, 0);
 	H[s] = n;
-	ec[t] = 1;//never set t to active...
+	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);
diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp
index 4c6a748..379c839 100644
--- a/content/graph/reroot.cpp
+++ b/content/graph/reroot.cpp
@@ -1,62 +1,48 @@
-// 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
+using W = ll; // edge weight type
+vector<vector<pair<int, W>>> adj;
+
 struct Reroot {
-	using T = ll;
+	using T = ll; // dp type
 
-	// 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) {}
+	static constexpr T E = 0; // neutral element
+	T takeChild(int v, int c, W w, T x) {} // move child along edge
+	static T comb(T x, T y) {}
+	T fin(int v, T x) {} // add v to own dp value x
 
-	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));
+	T dfs0(int v, int from = -1) {
+		T val = E;
+		for (auto [u, w] : adj[v]) {
+			if (u == from) continue;
+			val = comb(val, takeChild(v, u, w, dfs0(u, v)));
 		}
-		return dp[v] = fin(dp[v], v);
+		return dp[v] = fin(v, val);
 	}
 
-	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);
+	void dfs1(int v, int from = -1) {
+		vector<T> pref = {E};
+		for (auto [u, w] : adj[v]) {
+			pref.push_back(takeChild(v, u, w, dp[u]));
 		}
-		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);
+		auto suf = pref;
+		partial_sum(all(pref), pref.begin(), comb);
+		exclusive_scan(suf.rbegin(), suf.rend(),
+		               suf.rbegin(), E, comb);
+
+		for (int i = 0; i < sz(adj[v]); i++) {
+			auto [u, w] = adj[v][i];
+			if (u == from) continue;
+			dp[v] = fin(v, comb(pref[i], suf[i + 1]));
+			dfs1(u, v);
 		}
-		return res;
+		dp[v] = fin(v, suf[0]);
+	}
+
+	auto solve() {
+		dp.assign(sz(adj), E);
+		dfs0(0);
+		dfs1(0);
+		return dp;
 	}
 };
diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp
index ac9a40b..32f1099 100644
--- a/content/graph/scc.cpp
+++ b/content/graph/scc.cpp
@@ -1,11 +1,12 @@
-vector<vector<int>> adj, sccs;
-int counter;
+vector<vector<int>> adj;
+int counter, sccCounter;
 vector<bool> inStack;
 vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten.
 
 void visit(int v) {
 	int old = low[v] = counter++;
-	s.push_back(v); inStack[v] = true;
+	s.push_back(v);
+	inStack[v] = true;
 
 	for (auto u : adj[v]) {
 		if (low[u] < 0) visit(u);
@@ -13,20 +14,20 @@ void visit(int v) {
 	}
 
 	if (old == low[v]) {
-		sccs.push_back({});
+		sccCounter++;
 		for (int u = -1; u != v;) {
-			u = s.back(); s.pop_back(); inStack[u] = false;
-			idx[u] = sz(sccs) - 1;
-			sccs.back().push_back(u);
+			u = s.back();
+			s.pop_back();
+			inStack[u] = false;
+			idx[u] = sccCounter - 1;
 }}}
 
 void scc() {
 	inStack.assign(sz(adj), false);
 	low.assign(sz(adj), -1);
 	idx.assign(sz(adj), -1);
-	sccs.clear();
 
-	counter = 0;
+	counter = sccCounter = 0;
 	for (int i = 0; i < sz(adj); i++) {
 		if (low[i] < 0) visit(i);
 }}
diff --git a/content/graph/virtualTree.cpp b/content/graph/virtualTree.cpp
index 27d2d6c..6233b27 100644
--- a/content/graph/virtualTree.cpp
+++ b/content/graph/virtualTree.cpp
@@ -3,13 +3,13 @@ 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, n = sz(ind); i < n - 1; i++) {
-		ind.push_back(lca(ind[i], ind[i + 1]));
+	for (int i = 1, n = sz(ind); i < n; i++) {
+		ind.push_back(lca(ind[i - 1], ind[i]));
 	}
 	sort(all(ind), [&](int x, int y) {return in[x] < in[y];});
 	ind.erase(unique(all(ind)), ind.end());
 
-	int n = ind.size();
+	int n = sz(ind);
 	vector<vector<int>> tree(n);
 	vector<int> st = {0};
 	for (int i = 1; i < n; i++) {