考虑一个没有循环的图。图中有 K 个不同的对相互联系，如果我们想向所有人发送一封信。发送一封信需要一个单位时间。我们希望加快这一进程。那么这封信到达每个人(图节点(的最短时间是多少。我们可以将所有连接的组件交给任何连接的组件
他们的关键点是图形没有周期。因此，图形的每个组件都是一棵树。参见维基百科了解更多信息： https://en.wikipedia.org/wiki/Tree_(graph_theory(
让我们在下面假设，您的图形只有一个组件和n节点。如果您的图形有多个组件，只需取最大的一个并将n设置为该组件的节点数。
最坏的情况是，信件的传递从一个叶节点(底部(到根节点(顶部(，然后向下传递到另一个叶节点。此路径的长度为(n-1)。因此，这种交付需要(n-1)时间。
换句话说：具有n节点的树中的最长路径具有长度n-1。
使用动态规划来解决这类问题陈述。