Problem F
Chopping Trees
Languages
en
sv
After many years of research, Lolle has finally disproved
Lalexander’s conjecture (which stated that
Lolle now wants to bring home a particular tree. Each node
has bark on it. To be able to use the tree, he needs to peel
off the bark from each node and remove all branches. To peel
nodes and remove branches, he can perform a chop. To perform a chop, he chooses two nodes
Since Lolle isn’t keen on doing math anymore, he wants help finding the minimum number of chops needed to peel all nodes and remove all branches.
Input
The first line contains the integer
The following
Output
Print an integer: the minimum number of chops that Lolle needs to peel all nodes and remove all branches.
Points
Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.
Group |
Point value |
Constraints |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
At most |
|
|
No additional constraints. |
Explanation of sample 1:
At the beginning, the tree looks like this.
![\includegraphics[width=0.3\textwidth ]{1.png}](/problems/huggatrad/file/statement/en/img-0001.png)
If Lolle makes a chop where
![\includegraphics[width=0.3\textwidth ]{2.png}](/problems/huggatrad/file/statement/en/img-0002.png)
The remaining nodes that haven’t been chopped off are as follows:
![\includegraphics[width=0.3\textwidth ]{3.png}](/problems/huggatrad/file/statement/en/img-0003.png)
He can then chop along the nodes
![\includegraphics[width=0.3\textwidth ]{4.png}](/problems/huggatrad/file/statement/en/img-0004.png)
Explanation of sample 2:
Even if there aren’t any branches, the bark on node number
Sample Input 1 | Sample Output 1 |
---|---|
7 1 2 2 3 3 4 2 5 5 6 6 7 |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
1 |
1 |