查找訪問樹的所有節點的最小開銷

Question

給定每個邊都有相關成本的樹的根。查找訪問樹的每個節點的最低成本。

是來到我的腦海遞歸的解決方案是：當節點是節點遞歸地計算成本的每一個孩子℃的葉返回0

1. 基本情況。
2. 合計所有這些成本，並且還將兩次從節點到小孩的邊緣成本加起來（因爲我們需要回溯）。
3. 減去成本最高的孩子的邊緣成本（「貪婪」 - 我們不想從成本最高的孩子回溯）。

該方法是否正確？

有沒有更好的方法來解決問題？

Answer 1

1. 訪問從節點和返回該節點的所有子樹，這將花費所有edges * 2屬於該子樹。
2. 所以我們應該在樹中找到路徑成本最大的路徑。我們只是通過路徑，如果我們遇到了一些不在路徑中的節點，我們只是訪問它並且返回。 所以路徑中的邊只會訪問一次，剩下的邊將訪問兩次。
3. 如何找到成本最高的路徑？既然它是一棵樹，你可以遞歸地找到它。

答案應該是：

sum(cost(edge)*2) - sum(edge which in the path) 

---

我檢查你的解決方案，我認爲這是錯誤的（如果我誤解你的解決方案，請留言）：

減（「貪婪」 - 我們不希望從兒童回溯，成本最高）。

那孩子會是樹，有些邊緣必須訪問兩次。例如：

A 
/\ 
    B C 
/\ 
D E 

您無法訪問該子樹的所有邊一次訪問所有節點。

Answer 2

1-除最後一個葉節點外，所有節點路徑都將被訪問兩次。

2-我們將需要找出哪個葉節點具有最高的成本附加訪問根節點。

3-一旦我們發現這一點，我們將需要使我們的遍歷，使這個葉節點是最後訪問的節點。