Tree Diameter (Shpjegimi i zgjidhjes)

The diameter of a tree is the length of the longest path in the tree. In other words, we need to find two vertices $a$ and $b$ such that the distance between them is maximal.

To solve this problem, let’s use the following algorithm:

• First, perform a depth-first search starting from any vertex of the tree, for example, vertex $1$. During this traversal, find the vertex that is at the maximum distance from the starting point. Denote this vertex as $a$.

• Next, perform another depth-first search, this time starting from vertex $a$. As a result of this traversal, find the vertex that is farthest from $a$, and denote it as $b$.

Then, the distance between vertices $a$ and $b$ is the maximum among all pairs of vertices in the tree and, therefore, equals the diameter of the tree.

Example

Consider the tree from the example.

The diameter of the tree is $3$. The maximum distance is achieved, for example, between vertices $2$ and $5$.

Exercise

Find the diameter of the tree.

Algorithm implementation

Store the input tree in the adjacency list $g$. Store the shortest distances from the source to each vertex in the array $dist$.

vector<vector<int>> g;
vector<int> dist;

The dfs function performs a depth-first search from vertex $v$. The shortest distance from the source to vertex $v$ is $d$. The parent of vertex $v$ in the depth-first search is $p$.

void dfs(int v, int d, int p = -1)
{

Store the shortest distance from the source to vertex $v$ in dist[v].

  dist[v] = d;

Iterate over all edges (v, to). For each son to of vertex $v$ (where $to$ is not a parent of $v$) initiate a depth-first search. The distance from the source to vertex $to$ will be d + 1.

  for (int to : g[v])
    if (to != p) dfs(to, d + 1, v);
}

The main part of the program. Read the input data.

scanf("%d", &n);
g.resize(n + 1);
dist.resize(n + 1);

Construct an undirected tree.

for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

Find the shortest distances from vertex $1$ to all other vertices. The vertex farthest from it is $a$.

dfs(1, 0, -1);
a = max_element(dist.begin(), dist.begin() + n + 1) – 
                dist.begin();

Find the shortest distances from vertex $b$ to all other vertices. The vertex farthest from it is $b$.

dfs(a, 0,  -1);
b = max_element(dist.begin(), dist.begin() + n + 1) – 
                dist.begin();

Print the diameter of the tree — the shortest distance from $a$ to $b$.

printf("%d\n", dist[b]);