Orange Boy Can You Solve It Out? Ep. 47
Long time no see 思考题
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?
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
Solution by Orange Boy
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
来源：Hell Hole Studios Blog