[AGC004D] Teleporter 题解
简单贪心。
思路
可以发现一号节点必然连向自己。
由于题目中保证了最初每个点都可以到达一号节点。
那么我们发现改完一后，原图变成了一棵十分优美的树。
考虑在树上进行贪心。
我们贪心的从叶子结点往上走。
知道第 \(k\) 个若还没要到 \(1\)，就直接连向一号节点。
这个贪心也比较容易理解。
实现也很简单。
Code
AC记录。
简单贪心。
可以发现一号节点必然连向自己。
由于题目中保证了最初每个点都可以到达一号节点。
那么我们发现改完一后，原图变成了一棵十分优美的树。
考虑在树上进行贪心。
我们贪心的从叶子结点往上走。
知道第 \(k\) 个若还没要到 \(1\)，就直接连向一号节点。
这个贪心也比较容易理解。
实现也很简单。
AC记录。