From f03379490f14c22af9928260986e0891b27979b7 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sun, 27 Aug 2023 22:42:33 +0200
Subject: improved hld

---
 graph/hld.cpp | 22 +++++++++-------------
 1 file changed, 9 insertions(+), 13 deletions(-)

(limited to 'graph/hld.cpp')

diff --git a/graph/hld.cpp b/graph/hld.cpp
index 7e3331f..fae6030 100644
--- a/graph/hld.cpp
+++ b/graph/hld.cpp
@@ -7,7 +7,7 @@ void dfs_sz(int v = 0, int from = -1) {
 		dfs_sz(u, v);
 		sz[v] += sz[u];
 		if (adj[v][0] == from || sz[u] > sz[adj[v][0]]) {
-			swap(u, adj[v][0]);
+			swap(u, adj[v][0]); //changes adj!
 }}}
 
 void dfs_hld(int v = 0, int from = -1) {
@@ -25,24 +25,20 @@ void init(int root = 0) {
 	sz.assign(n, 1), nxt.assign(n, 0), par.assign(n, -1);
 	in.resize(n), out.resize(n);
 	counter = 0;
-	dfs_sz(root); dfs_hld(root);
+	dfs_sz(root);
+	dfs_hld(root);
 }
 
-vector<pair<int, int>> get_intervals(int u, int v) {
-	vector<pair<int, int>> res;
-	while (true) {
+template<typename F>
+void for_intervals(int u, int v, F&& f) {
+	for (;; v = par[nxt[v]]) {
 		if (in[v] < in[u]) swap(u, v);
-		if (in[nxt[v]] <= in[u]) {
-			res.emplace_back(in[u], in[v] + 1);
-			return res;
-		}
-		res.emplace_back(in[nxt[v]], in[v] + 1);
-		v = par[nxt[v]];
+		f(max(in[u], in[nxt[v]]), in[v] + 1);
+		if (in[nxt[v]] <= in[u]) return;
 }}
 
 int get_lca(int u, int v) {
-	while (true) {
+	for (;; v = par[nxt[v]]) {
 		if (in[v] < in[u]) swap(u, v);
 		if (in[nxt[v]] <= in[u]) return u;
-		v = par[nxt[v]];
 }}
-- 
cgit v1.2.3