From db64838afe7f333d45f3c76c8e72aea89ccbf52a Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
Date: Sat, 9 Mar 2024 19:35:04 +0100
Subject: virtual trees

---
 graph/virtualTree.cpp | 25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)
 create mode 100644 graph/virtualTree.cpp

(limited to 'graph/virtualTree.cpp')

diff --git a/graph/virtualTree.cpp b/graph/virtualTree.cpp
new file mode 100644
index 0000000..f7a3cb1
--- /dev/null
+++ b/graph/virtualTree.cpp
@@ -0,0 +1,25 @@
+// needs dfs in- and out- time and lca function
+vector<int> in, out;
+
+void virtualTree(const vector<int>& a) { // takes indices of used nodes
+	auto ind = a;
+	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);
+	stack<int> st{{0}};
+	for (int i=1; i<n; i++) {
+		while (in[ind[i]] >= out[ind[st.top()]]) st.pop();
+		tree[st.top()].push_back(i);
+		st.push(i);
+	}
+
+	// virtual directed tree with n nodes, original indices in ind
+	// weights can be calculated if necessary, e.g. with binary lifting
+}
-- 
cgit v1.2.3