11430. Tree distances I

You are given a tree consisting of n nodes.

Your task is to determine for each node the maximum distance to another node.

Input. The first line contains an integer n (1 ≤ n ≤ 2 * 10⁵) – the number of nodes. The nodes are numbered 1, 2, ..., n.

Then there are n – 1 lines describing the edges. Each line contains two integers a and b (1 ≤ a, b ≤ n) – there is an edge between nodes a and b.

Output. Print n integers: for each node 1, 2, ..., n the maximum distance to another node.

Sample input	Sample output
5 1 2 1 3 3 4 3 5	2 3 2 3 3

РЕШЕНИЕ

graphs – depth first search

Algorithm analysis

Using two depth first searches, find the diameter of the tree. Since the tree is a connected graph with no cycles, both depth first and breadth first search will find the shortest distances from the source (starting vertex).

Let a and b be two vertices located at the maximum distance from each other. Let’s find the shortest distances from a and b to the remaining vertices in the dista and distb arrays. Then the greatest distance from vertex i to another vertex is equal to

max(dista[i], distb[i])

Example

Consider a tree from the sample.

The diameter of the tree will be, for example, the distance between vertices 2 and 5.

Algorithm realization

Store the input tree in the adjacency list g. Store the shortest distances from vertices a and b in the arrays dista and distb.

vector<vector<int>> g;

vector<int> dista, distb;

Read the number of the nodes n in the tree.

scanf("%d", &n);

The function dfs performs a depth first search from the vertex v. The shortest distance from the source to the vertex v is d. The shortest distances from the source to the vertices are stored in the array dist. The parent of the vertex v in depth first search is p.

void dfs(int v, int d, vector<int>& dist, int p = -1)

{

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

dist[v] = d;

for (int i = 0; i < g[v].size(); i++)

{

Iterate through the edges (v, to). For each son to of the vertex v (vertex to is not a parent of the vertex v) start a depth first search.

int to = g[v][i];

if (to != p) dfs(to, d + 1, dist, v);

}

}

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

scanf("%d", &n);

g.resize(n + 1);

dista.resize(n + 1);

distb.resize(n + 1);

Construct the 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 the vertex 1. The farthest vertex from 1 is vertex a.

dfs(1, 0, dista, -1);

a = max_element(dista.begin() + 1, dista.begin() + n + 1) - dista.begin();

Find the shortest distances from the vertex a and store them in the array dista. The farthest vertex from a is the vertex b. The distance from a to b is the diameter of the graph.

dfs(a, 0, dista, -1);

b = max_element(dista.begin() + 1, dista.begin() + n + 1) - dista.begin();

Find the shortest distances from the vertex b and store them in the array distb.

dfs(b, 0, distb, -1);

For each vertex i print the farthest vertex.

for (i = 1; i <= n; i++)

printf("%d ", max(dista[i], distb[i]));

printf("\n");