CSES - Finding a Centroid

Time Complexity: $\mathcal O(N)$

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

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;