A13225 | $Three Paths on a Tree$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

You are given an unweighted tree with $n$ vertices. Recall that a tree is a connected undirected graph without cycles. Your task is to choose three distinct vertices $a, b, c$ on this tree such that the number of edges which belong to at least one of the simple paths between $a$ and $b$ , $b$ and $c$ , or $a$ and $c$ is the maximum possible. See the notes section for a better understanding. The simple path is the path that visits each vertex at most once.

The first line contains one integer number $n$ ( $3 \le n \le 2 \cdot 10^5$ ) — the number of vertices in the tree. Next $n - 1$ lines describe the edges of the tree in form $a_i, b_i$ ( $1 \le a_i$ , $b_i \le n$ , $a_i \ne b_i$ ). It is guaranteed that given graph is a tree.

In the first line print one integer $res$ — the maximum number of edges which belong to at least one of the simple paths between $a$ and $b$ , $b$ and $c$ , or $a$ and $c$ . In the second line print three integers $a, b, c$ such that $1 \le a, b, c \le n$ and $a \ne, b \ne c, a \ne c$ . If there are several answers, you can print any.

输入 #1

输出 #1

5
1 8 6

C++ 编辑器

输入

输出