問題一覧 > 通常問題

No.1928 Make a Binary Tree

レベル : / AI推定難易度 : 1925 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 43
作問者 : harurun / テスター : 👑 Kazun
お気に入りにしたユーザー ProblemId : 7403 / 自分の提出
問題文最終更新日: 2022-05-07 12:26:21
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 342 (順位表) の他の問題:

The difficulty was changed to ★3.5 after the contest ended.

Problem Statement

There is a rooted tree with $N$ vertices, numbered $1\sim N$. The root is vertex $1$.

The $i$-th edge connects vertex $x_i$ and vertex $y_i$.

You may perform each of the following operations any number of times, in any order.

  • Operation A: Choose a vertex $v$. Let vertex $u$ be the parent of vertex $v$, and let vertex $w$ be some ancestor of vertex $u$. Delete the edge connecting $v$ and $u$, and add an edge connecting $v$ and $w$.
  • Operation B: Choose a vertex $v$. Let vertex $u$ be the parent of vertex $v$. Delete the edge connecting $v$ and $u$, and delete all edges and vertices contained in the subtree rooted at $v$.
  • (Deleted edges and vertices cannot be used. Also, the operations cannot be performed if $v$ has no parent.)

Your goal is to use these operations to create a binary tree rooted at vertex $1$ with as many vertices as possible.

Find the maximum number of vertices of the binary tree you create.


▼What is an ancestor of vertex $v$? The vertices on the shortest path between vertex $v$ and the root are called the ancestors of vertex $v$.

Input

$N$
$x_1\ y_1$
$\vdots$
$x_{N-1}\ y_{N-1}$
  • Line $1$ gives the number of vertices $N$.
  • Lines $2\sim N$ give $x_i$ and $y_i$, separated by a space.

Constraints

  • $1≤N≤2\times 10^5$
  • $1≤x_i,y_i≤N$
  • All inputs are integers.
  • The given graph is a tree.

Output

Output the answer on 1 line. End the output with a newline.

Sample

Sample 1
Input
4
1 2
1 3
3 4
Output
4

The given tree is a binary tree. Therefore, the maximum is achieved when no operations are performed.

Sample 2
Input
4
1 2
1 3
1 4
Output
3

Performing operation B on vertex $4$ yields a binary tree, and this is the maximum.

Sample 3
Input
5
1 2
2 3
2 4
2 5
Output
5

The maximum is achieved by performing operation A on vertex $5$, connecting it to its ancestor, vertex $1$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。