CSES - Finding a Centroid

C++

Copy
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
int n;                // number of nodes
vector<int> g[maxn];  // graph
int s[maxn];          // size of subtree

void dfs_size(int cur, int par) {
	s[cur] = 1;

Java

Copy
import java.io.*;
import java.util.*;

public class Centroid {
	private static int n;  // number of nodes
	private static List<List<Integer>> graph;
	private static int[] sub_array_size;

	private static void dfs_size(int curr, int prev) {
		// size of a subtree is the sum of the sizes of all child subtrees + 1.

Python

Copy
MAX_N = 200000
g = [[] for i in range(MAX_N + 1)]  # graph
subtree_size = [0 for i in range(MAX_N + 1)]  # size of subtree


def dfs_size(curr: int, parent: int) -> None:
	"""calculates all subtree sizes (sum of child sizes + 1)"""
	subtree_size[curr] = 1
	for child in g[curr]:
		if child != parent: