From f9c565f924361ff8565006f7d86372c2591664e4 Mon Sep 17 00:00:00 2001
From: Noobie99 <noob999noob999@gmail.com>
Date: Sun, 28 May 2023 22:43:52 +0200
Subject: minor changes + fix lca in hld

---
 graph/hld.cpp | 32 ++++++++++++++------------------
 1 file changed, 14 insertions(+), 18 deletions(-)

(limited to 'graph/hld.cpp')

diff --git a/graph/hld.cpp b/graph/hld.cpp
index 9431782..7e3331f 100644
--- a/graph/hld.cpp
+++ b/graph/hld.cpp
@@ -1,35 +1,31 @@
 vector<vector<int>> adj;
 vector<int> sz, in, out, nxt, par;
-int t;
+int counter;
 
 void dfs_sz(int v = 0, int from = -1) {
-	sz[v] = 1;
-	for (auto& u : adj[v]) {
-		if (u != from) {
-			dfs_sz(u, v);
-			sz[v] += sz[u];
-		}
+	for (auto& u : adj[v]) if (u != from) {
+		dfs_sz(u, v);
+		sz[v] += sz[u];
 		if (adj[v][0] == from || sz[u] > sz[adj[v][0]]) {
 			swap(u, adj[v][0]);
 }}}
 
 void dfs_hld(int v = 0, int from = -1) {
 	par[v] = from;
-	in[v] = t++;
-	for (int u : adj[v]) {
-		if (u == from) continue;
-		nxt[u] = (u == adj[v][0] ? nxt[v] : u);
+	in[v] = counter++;
+	for (int u : adj[v]) if (u != from) {
+		nxt[u] = (u == adj[v][0]) ? nxt[v] : u;
 		dfs_hld(u, v);
 	}
-	out[v] = t;
+	out[v] = counter;
 }
 
-void init() {
+void init(int root = 0) {
 	int n = sz(adj);
-	sz.assign(n, 0); in.assign(n, 0); out.assign(n, 0);
-	nxt.assign(n, 0); par.assign(n, -1);
-	t = 0;
-	dfs_sz(); dfs_hld();
+	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);
 }
 
 vector<pair<int, int>> get_intervals(int u, int v) {
@@ -47,6 +43,6 @@ vector<pair<int, int>> get_intervals(int u, int v) {
 int get_lca(int u, int v) {
 	while (true) {
 		if (in[v] < in[u]) swap(u, v);
-		if (in[nxt[v]] <= in[u]) return in[u];
+		if (in[nxt[v]] <= in[u]) return u;
 		v = par[nxt[v]];
 }}
-- 
cgit v1.2.3