From a7f4c162112a1f80b823984baa0c737df9a7f5e0 Mon Sep 17 00:00:00 2001
From: f1or1an <110727007+f1or1an@users.noreply.github.com>
Date: Wed, 15 Nov 2023 03:44:56 +0100
Subject: hld: fix bug

Nach Initialisierung mit root!=0 war nxt[root]!=root.
Dadurch gab es (mindestens, aber nicht nur) diesen Fehler:
Beim Aufruf von for_intervals mit u=v=root wurde f mit
max(in[root], in[nxt[root]]
=max(0, in[0])
=in[0],
einer quasi beliebigen Zahl, aufgerufen
---
 graph/hld.cpp | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'graph/hld.cpp')

diff --git a/graph/hld.cpp b/graph/hld.cpp
index fae6030..65d3f5c 100644
--- a/graph/hld.cpp
+++ b/graph/hld.cpp
@@ -22,7 +22,7 @@ void dfs_hld(int v = 0, int from = -1) {
 
 void init(int root = 0) {
 	int n = sz(adj);
-	sz.assign(n, 1), nxt.assign(n, 0), par.assign(n, -1);
+	sz.assign(n, 1), nxt.assign(n, root), par.assign(n, -1);
 	in.resize(n), out.resize(n);
 	counter = 0;
 	dfs_sz(root);
-- 
cgit v1.2.3