Special Ice Breaking Penguin
Time limit1sMemory limit1024 MB
Given a tree with some nodes marked as supports, break as many nodes as possible while keeping the penguin's node connected to at least two supports through unbroken ordinary nodes.
- Level
Hard8 of 10
- Topics
- Tree, DFS, Greedy, Dynamic programming
- Solved
- No attempts yet
Problem
Dodo was bored, so he went to a board game cafe. A board game called Special Ice Breaking Penguin, an upgraded version of the Ice Breaking Penguin he used to enjoy, had just come out, so he decided to play it himself. The game comes with special glasses, and when you wear them and look at the ice, you can see the connections between the ice blocks.
There are two kinds of ice in Special Ice Breaking Penguin: ice that acts as a support and ordinary ice. Ice that acts as a support appears red, and it holds up ordinary ice so that the ordinary ice does not break. An ordinary ice block does not break even if only one support is connected to it, but the ice block the penguin is standing on does not break only if two or more ice blocks acting as supports are connected to it. Here, a support being connected means that a connection path leads from the support through distinct ordinary ice blocks. In Special Ice Breaking Penguin, what is the maximum number of ice blocks Dodo can break without dropping the penguin?

Input
The first line gives the number of ice blocks (), the number of ice blocks that act as supports (), and the number of the ice block the penguin is on (). When the number of ice blocks that act as supports is , ice blocks through act as supports.
Each of the next lines gives two integers and . This means ice block and ice block are connected, and the same connection is not given more than once.
When the game starts, the penguin is on an ordinary ice block and no ice block is broken. Each ice block has an integer number from to , and there is exactly one path between any two distinct ice blocks. Also, there is no case where two distinct supports are connected without passing through the ice block the penguin is on.
Output
Find the maximum number of ice blocks the player can break without dropping the penguin. Ice blocks that act as supports also count as ice blocks that can be broken.