minor changes + fix lca in hld

1 files changed, 13 insertions, 14 deletions

diff --git a/graph/centroid.cpp b/graph/centroid.cpp
index d2855e2..c5187a5 100644
--- a/graph/centroid.cpp
+++ b/graph/centroid.cpp
@@ -1,22 +1,21 @@
 vector<int> s;
-void dfs1(int u, int v = -1) {
-	s[u] = 1;
-	for (int w : adj[u]) {
-		if (w == v) continue;
-		dfs1(w, u);
-		s[u] += s[w];
+void dfs_sz(int v, int parent = -1) {
+	s[v] = 1;
+	for (int u : adj[v]) if (u != parent) {
+		dfs_sz(u, v);
+		s[v] += s[u];
 }}
 
-pair<int, int> dfs2(int u, int v, int n) {
-	for (int w : adj[u]) {
-		if (2 * s[w] == n) return {u, w};
-		if (w != v && 2 * s[w] > n) return dfs2(w, u, n);
+pair<int, int> dfs_cent(int v, int parent, int n) {
+	for (int u : adj[v]) if (u != parent) {
+		if (2 * s[u] == n) return {v, u};
+		if (2 * s[u] > n) return dfs_cent(u, v, n);
 	}
-	return {u, -1};
+	return {v, -1};
 }
 
 pair<int, int> find_centroid(int root) {
-	// s muss nicht initialisiert werden, nur groß genug sein
-	dfs1(root);
-	return dfs2(root, -1, s[root]);
+	s.resize(sz(adj));
+	dfs_sz(root);
+	return dfs_cent(root, -1, s[root]);
 }