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.

#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;

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!