Centroid

Competitive Programming

Definition

In a tree , a centroid is a node which if we remove (remove it and remove all edges from this node) , the maximum size of the trees in the newly created forest will be the minimum .

The implementation is straightfowrad . Just implement according to the definition . 

1
2
3
4
Step 1 : Find the size of all subtrees connected to a vertex
Step 2 : Find the largest among all the ones found in step 1
Step 3 : Among all ones found in step 2 , find the minimum size . 
Step 4 : The minimum size is found in step 3 is indeed caused by the removal of centroid . So , we have found our centroid
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void dfs(int u,int p)
{
    sz[u] = 1;

    for(int v:adj[u])
    {
        if(v==p)
            continue;

        dfs(v,u);

        sz[u] += sz[v];
        mxCCsz[u] = max(mxCCsz[u],sz[v]); /// considering all the component rooted at children
    }

    mxCCsz[u] = max(mxCCsz[u],n-sz[u]); /// the one component rooted at the parent
}

vector<int> find_centroids()
{
    dfs(1,-1);

    int mn = INT_MAX;
    for(int i=1; i<=n; i++)
        mn = min(mn,mxCCsz[i]);

    vector<int>centroids;
    for(int i=1; i<=n; i++)
        if(mxCCsz[i]==mn)
            centroids.push_back(i);

    return centroids;
}

Extended Definition

In a tree , a centroid is a node which if we remove (remove it and remove all edges from this node) , the size of the trees in the newly created forest will be atmost N/2

This definition actually gives what the size of the trees in the newly created forest will . It will be atmost N/2

Implementation using this extended definition .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void dfs(int u,int p,vector<int>&centroids)
{
    bool isCentroid = true;

    sz[u] = 1;
    for(int v:adj[u])
    {
        if(v==p)
            continue;

        dfs(v,u,centroids);

        sz[u] += sz[v];

        if(sz[v] > n/2) isCentroid = false; /// considering all the component rooted at children
    }

    if(n-sz[u] > n/2) isCentroid = false; /// the one component rooted at the parent

    if(isCentroid) centroids.push_back(u);
}

vector<int> find_centroids()
{
    vector<int>centroids;
    dfs(1,-1,centroids);

    return centroids;
}

Number of Centroids

We can see that if we remove the centroid , each of the trees in the remaining forest can have atmost N/2 nodes .

Now consider this 2 cases :

Case 1

Subtree size of centroid > N/2

This case we can not have more than one centroid because if there were to have another centroid , this component of the first centroid ( which has subtree size > N/2 ) will have more than N/2 nodes . And thus defying the condition to be a centroid . So , we can not have more than 1 centroids in this case .

Case 2

Subtree size of centroid = N/2

In this case , the size of the component including the parent of this centroid will also be N/2 . Thus , we can get 2 centroids in this case

So , we can have atmost 2 centroids in a tree