填充树的 Dp 方法和递归
Dp approach and recurrence for filling tree
我有这个问题：
我们需要向树中的所有节点传播一个消息，使得树节点中的所有节点都知道这个消息。在单轮中，任何知道该消息的节点都可以将其转发给它的任何子节点。设计一种算法，计算所有节点接收消息所需的最小轮数。
这应该可以通过动态规划算法解决。
和一些示例输入：
input
1 2
1 3
2 4
2 5
2 6
3 7
4 8
4 9
7 10
7 11
11 12
output
5
我对这个问题的代码实现不太感兴趣，但更感兴趣的是一般方法、递归关系的想法，或者可能是关于什么是最佳子结构的想法。
我的想法
我想过可以通过 bellman-ford 式的方法解决这个问题，但很快就没有任何意义了。
另一种方法是从顶部开始，计算从根到它的两个子节点的最小轮数，然后以某种方式向下递归。
谁能帮帮我？也许递归方法也有助于更接近解决方案
传播的最短时间是多少？它是树的高度，因此请将每个子树的高度作为其成本。
是什么增加了传播时间？如果 2 个子树的高度相同，我们必须选择其中一个。所以用一个增加最高高度的成本，一定要检查一个节点的所有子树是否有唯一的成本。从下往上开始。 parent 的成本是 max(subtrees)+1.
首先将消息传播到成本最高的子树。
因此在您的示例中，右子树没有问题，因为没有子树具有与其他子树相同的值。
最左边的子树有两个高度都为0的子树，所以增加1个子树的代价，现在最左边的子树最大子树的代价为1，为parent的代价为+1，所以代价为2。它的 parent 有问题，它的树子树中有两个子树的高度都是 0，所以一比一增加，最大成本是 max(subtrees) 是 2 + 1 对于 parent 成本 3.
这给根留下了一个问题，现在有两个子树的成本为 3，因此将最高子树的成本增加 1 到 4，这使根的成本为 5。
除了一个细节，这将完全按照示例进行，第4轮也会将最后一个节点填充到右侧，该示例中只填充了第5个（可能是错误的）。
我有这个问题：
我们需要向树中的所有节点传播一个消息，使得树节点中的所有节点都知道这个消息。在单轮中，任何知道该消息的节点都可以将其转发给它的任何子节点。设计一种算法，计算所有节点接收消息所需的最小轮数。
这应该可以通过动态规划算法解决。 和一些示例输入：
input
1 2
1 3
2 4
2 5
2 6
3 7
4 8
4 9
7 10
7 11
11 12
output
5
我对这个问题的代码实现不太感兴趣，但更感兴趣的是一般方法、递归关系的想法，或者可能是关于什么是最佳子结构的想法。
我的想法
我想过可以通过 bellman-ford 式的方法解决这个问题，但很快就没有任何意义了。
另一种方法是从顶部开始，计算从根到它的两个子节点的最小轮数，然后以某种方式向下递归。
谁能帮帮我？也许递归方法也有助于更接近解决方案
传播的最短时间是多少？它是树的高度，因此请将每个子树的高度作为其成本。
是什么增加了传播时间？如果 2 个子树的高度相同，我们必须选择其中一个。所以用一个增加最高高度的成本，一定要检查一个节点的所有子树是否有唯一的成本。从下往上开始。 parent 的成本是 max(subtrees)+1.
首先将消息传播到成本最高的子树。
因此在您的示例中，右子树没有问题，因为没有子树具有与其他子树相同的值。
最左边的子树有两个高度都为0的子树，所以增加1个子树的代价，现在最左边的子树最大子树的代价为1，为parent的代价为+1，所以代价为2。它的 parent 有问题，它的树子树中有两个子树的高度都是 0，所以一比一增加，最大成本是 max(subtrees) 是 2 + 1 对于 parent 成本 3.
这给根留下了一个问题，现在有两个子树的成本为 3，因此将最高子树的成本增加 1 到 4，这使根的成本为 5。
除了一个细节，这将完全按照示例进行，第4轮也会将最后一个节点填充到右侧，该示例中只填充了第5个（可能是错误的）。