No.3206 U s h i t a U n i T r e e A - k u n (lol)
問題文最終更新日: 2025-07-18 16:35:09
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 474
(順位表)
の他の問題:
Problem Statement
You are given an undirected tree $T$ with $N$ vertices. The vertices are numbered $1, 2, \cdots, N$, and for each $i \ (1 \leq i \leq N-1)$, the $i$-th edge connects vertex $u_i$ and vertex $v_i$.
A graph for which there exists a vertex $x$ satisfying the following conditions is called a beautiful sea urchin tree.
- The graph is an undirected tree.
- Let $S$ be the set of leaves of the rooted tree with vertex $x$ as the root. Then all of the following conditions are satisfied.
- For any pair of distinct vertices $(u, v)$ in $S$, their lowest common ancestor is $x$.
- For $u \in S$, the distances $d(x, u)$ between $x$ and $u$ are all equal.
On the other hand, the following graphs are not beautiful sea urchin trees.
Find the maximum number of vertices of a beautiful sea urchin tree among the subgraphs of $T$. Note that under the constraints of this problem, a beautiful sea urchin tree exists among the subgraphs of $T$.
Constraints
Input
$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
Output
Find the maximum number of vertices of a beautiful sea urchin tree.
Sample
Sample 1
Input
8 1 2 2 3 2 4 2 5 5 6 5 7 5 8
Output
5
Sample 2
Input
2 1 2
Output
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。