CSES - Finding a Centroid
Authors: Dong Liu, Paul Chen, Raviteja Kompalli
Time Complexity:
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 nodesvector<int> g[maxn]; // graphint s[maxn]; // size of subtreevoid 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 nodesprivate 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 = 200000g = [[] for i in range(MAX_N + 1)] # graphsubtree_size = [0 for i in range(MAX_N + 1)] # size of subtreedef dfs_size(curr: int, parent: int) -> None:"""calculates all subtree sizes (sum of child sizes + 1)"""subtree_size[curr] = 1for child in g[curr]:if child != parent:
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!