CSES - Finding a Centroid

Authors: Dong Liu, Paul Chen, Raviteja Kompalli


Time Complexity: O(N)\mathcal O(N)

For more information about centroids and how to find/use them, see their module.

C++

#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

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

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:
dfs_size(child, curr)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!