Diameter of any tree and applications

If there is a tree with N nodes. TO calculate the diameter,

1. Run bfs from any node and find the farthest node (say X) , this can be seen as a leaf node.

2. From X, run another bfs to find the farthest node form it. (Say Y).

3. The distance between X and Y is longest distance.

There can be many pair of nodes with the longest distance.

Application:

This can be used of find the best and worst nodes in the tree. Best node is the node, which if we make the root, the height of tree is minimised.

To find worst, find the pair of nodes with maximum distance. These are the worst nodes.

To find the best, find the nodes at half the distance of the maximum from the worst nodes.

To find the longest distance  

Code :

#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000
vector < int > g[MAXN + 1];
int maxWt[MAXN + 1];
bool check[MAXN + 1];
void bfs(int n)
{
    queue <pair<int, int> > q;
    q.push(make_pair(n, 0));
    while (!q.empty())
    {
        int root = q.front().first;
        int wt = q.front().second;
        check[root] = true;
        for(int i = 0; i<g[root].size(); i++)
        {
            if (!check[g[root][i]])
            {
                q.push(make_pair(g[root][i], wt + 1));
            }
        }
        maxWt[root] = wt;
        q.pop();
    }
}
int main()
{
    int n,a,b;
    cin>>n;
    vector<pair<int,int> > v[n+9];
    for(int i=0;i<n-1;i++)
    {
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bfs(1);
    int maxRoot = 0;
    for(int i = 1; i<= n; i++)
        maxRoot = maxWt[maxRoot] < maxWt[i] ? i : maxRoot;
    memset(maxWt, 0, sizeof(maxWt));
    memset(check, 0, sizeof(check));
    bfs(maxRoot);
    maxRoot = 0;
    for(int i = 1; i<= n; i++)
        maxRoot = max(maxRoot, maxWt[i]);
    cout<<maxRoot<<endl;
    return 0;
}