Open Wizmann opened 4 years ago
Problem Code
给定一棵有N个节点的树。一个人从节点1开始遍历这棵树，此时时间为0。直到所有的点都被遍历过，并且人回到了节点1，遍历结束。从一个节点走到相邻节点，花费时间1。
如果人在节点k，此时的时间为t，那么我们将这个状态记作{k, t}。 现在我们有一个时光机，我们可以将{k, t}状态倒回到任意{k, t1}，0 <= t1 < t。使用时光机有一个限制，所有的{k, t}状态不能重复，否则会导致宇宙的坍缩。
{k, t}
{k, t1}
问遍历完成这棵树最短需要多少时间。
为什么不直接看题解呢？
我们可以通过范例了解一种遍历树的方式。
看不懂就照着样例自己走一遍，这里没有高科技。
我们可以看到，每一个度为d的节点，最多会被访问d次。那么我们将这d次的时间值记为[0, 1, 2 ... d]，就可以解决这个问题了。
这个问题思路还是比较简单的，问题在于实现。因为我们可以在任意的状态进行时间回溯。肯定要设计一种策略。
假设我们有节点p，第一次访问这个节点的时间为t。那么我们访问其子节点时，可以要求其返回时间为[1, 2 ... t - 1, t + 1...d]。
剩下就是DFS的实现了。这题本质上是一道实现题。
Problem Code
题意
给定一棵有N个节点的树。一个人从节点1开始遍历这棵树，此时时间为0。直到所有的点都被遍历过，并且人回到了节点1，遍历结束。从一个节点走到相邻节点，花费时间1。
如果人在节点k，此时的时间为t，那么我们将这个状态记作
{k, t}。 现在我们有一个时光机，我们可以将{k, t}状态倒回到任意{k, t1}，0 <= t1 < t。使用时光机有一个限制，所有的{k, t}状态不能重复，否则会导致宇宙的坍缩。问遍历完成这棵树最短需要多少时间。
解法
我们可以通过范例了解一种遍历树的方式。
我们可以看到，每一个度为d的节点，最多会被访问d次。那么我们将这d次的时间值记为[0, 1, 2 ... d]，就可以解决这个问题了。
这个问题思路还是比较简单的，问题在于实现。因为我们可以在任意的状态进行时间回溯。肯定要设计一种策略。
假设我们有节点p，第一次访问这个节点的时间为t。那么我们访问其子节点时，可以要求其返回时间为[1, 2 ... t - 1, t + 1...d]。
剩下就是DFS的实现了。这题本质上是一道实现题。