1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23

namespace centroid {
    int sz[MX], cpar[MX];
    bitset<MX> vis;
	void dfs(vector<int> * G, int u, int p = 0) {
		sz[u] = 1;
		for (int v : G[u]) if (v != p && !vis[v]) dfs(G, v, u), sz[u] += sz[v];
	}
	int centroid(vector<int> * G, int u) {
		dfs(G, u);
		int num = sz[u], p = 0;
		do {
			int nxt = 0;
			for (int v : G[u]) if (v != p && !vis[v] && 2*sz[v] > num) nxt = v;
			p = u, u = nxt;
		} while (u);
		return p;
	}
	void centroid_decomp(vector<int> * G, int u = 1, int p = 0) {
		int c = centroid(G, u);
		vis[c] = 1,	cpar[c] = p;
		for (int v : G[c]) if (!vis[v]) centroid_decomp(G, v, c);
	}
}