問題一覧 > 通常問題

No.3206 U s h i t a U n i T r e e A - k u n (lol)

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 73
作問者 : amesyu / テスター : noshinn lmorinn 👑 qand
お気に入りにしたユーザー ProblemId : 12320 / 自分の提出
問題文最終更新日: 2025-07-18 16:35:09
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.
For example, the following graphs are beautiful sea urchin trees. As an example, a vertex $x$ satisfying the conditions is shown in navy blue.

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

  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq u_i \lt v_i \leq N$
  • The given graph is an undirected tree.
  • All input values are integers.
  • 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もしくは右上の雲マークをクリックしてアカウントを作成してください。