No.1928 Make a Binary Tree
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
harurun
Kazun