Solved!
Difficulty: Div2D

Long time no see 思考题

Tree Traversing

Hikari has a tree of N nodes. The node #1 is the root. Initially she is at node 1.

She can do one of the following three operations:
- Move to any adjacant node with cost 1
- Mark current node as temporary start with 0 cost. There can only be at most 1 temporary start at any moment.
- Teleport to temporary start or node 1 with 0 cost

What's the minimum cost to visit every node in the tree?

Example

Answer = 5

• Go to node 2
• Go to node 3
• Go to node 4
• Mark as temporary start(4)
• Go to node 5
• Teleport to temporary start(4)
• Go to node 6
  =5

Solution

By MonkeyKing:

dp(n,2,2) represents

currently at node x, is it needed to traval back to.x, do we have extra temporary start to put

then if we have an extra temporary start, we can choose for every son if we put a extra temporary start there or just teleport back to x