这个问题几乎等同于最小和子序列问题,并且可以通过动态规划以类似的方式解决。
我们将使用 DF 搜索计算以下数组:
dw1[i] = minimum sum achievable by only using node i and its descendants.
pw1[i] = predecessor of node i in the path found for dw1[i].
dw2[i] = second minimum sum achevable by only using node i and its descendants,
a path that is edge-disjoint relative to the path found for dw1[i].
如果你能计算出这些,min(dw1[k], dw1[k] + dw2[k])
接管所有k
。这是因为您的路径将采用以下基本形状之一:
k k
| or / \
| / \
|
所有这些都包含在我们收取的金额中。
计算 dw1
从根节点运行 DFS。在 DFS 中,跟踪当前节点及其父节点。在每个节点上,假设它的子节点是d1, d2, ... dk
。然后dw1[i] = min(min{dw1[d1] + cost[i, d1], dw1[d2] + cost[i, d2], ..., dw1[dk] + cost[i, dk]}, min{cost[i, dk]})
。为叶节点设置dw1[i] = 0
。不要忘记pw1[i]
使用选定的前任进行更新。
计算 dw2
从根节点运行 DFS。做同样的事情dw1
,除了从一个节点i
到它的一个子节点时k
,只更新dw2[i]
if pw1[i] != k
。但是,您为所有孩子递归地调用该函数。在伪代码中看起来像这样:
df(node, father)
dw2[node] = inf
for all children k of node
df(k, node)
if pw1[node] != k
dw2[node] = min(dw2[node], dw1[k] + cost[node, k], cost[node, k])