Find Centroid

const int N = 1e5 + 2;
int cnt[N];
vector<pair<int, int>> adj[N];
bool inused[N];

void dfs_cnt(int v, int p = -1)
{
    cnt[v] = 1;
    for (auto i : adj[v])
        if (i.first != p && inused[i.second])
            dfs_cnt(i.first, v),
                cnt[v] += cnt[i.first];
}

int Find_Centroid(int root)
{
    dfs_cnt(root);
    int centroid = root;
    while (1)
    {
        int t, v = 0;
        for (auto i : adj[centroid])
            if (inused[i.second] && cnt[i.first] <= cnt[centroid])
            {
                if (cnt[i.first] > v)
                {
                    v = cnt[i.first];
                    t = i.first;
                }
            }
        if (v <= cnt[root] / 2)
            return centroid;
        centroid = t;
    }
}