Yet another tree problem

You are given a tree, that is, an undirected, connected graph with no
cycles. You may choose any starting vertex, move around the tree step by
step (from the current vertex to any adjacent vertex), visit every
vertex at least once, and end your travel anywhere. What is the minimum
number of steps to do so?

Input

Input consists of several cases, each with the number n of vertices of
the tree, followed by n − 1 pairs x y denoting an edge between x and y.
Assume 2 ≤ n ≤ 10⁵, that vertices are numbered between 1 and n, and that
the given edges indeed form a tree.

Output

For every graph, print the minimum number of steps to visit the whole
tree.

Problem information

Author: Manuel Torres
Event: Vint-i-quatrè Concurs de Programació de la UPC - Semifinal
Date: 2026-06-18

Generation: 2026-06-10T22:55:34.453Z

© Jutge.org, 2006–2026.
https://jutge.org
