最小的數字。程序在C++

Question

• 有點W點和W-1點之間的連接。每個點都連接在一起。每個連接的長度爲1。 計算機程序可以爲某些點增加值1或2。
• 如果程序將1到點A，那麼每點與被連接到A（包括點A）將被塗成紅色
• 如果程序添加2，然後用連接至某個點與被連接到A每一點並且連接到A和點A的每個點都將被塗成紅色。 我需要畫所有點。 等等。
• 我寫入控制檯自然編號W。在下一個W-1行我寫連接點的數字對。
• 計劃schould schow我加入到分

舉例而言，所有值的控制檯總和最小

我寫

6

1 2

2 3

3 4

3 5

3 6

結果是2

Answer 1

所以，如果我理解這個權利，你有：
一些點/節點，並在表格開始 - 連接>端。
你想要的最小和可能的標記的所有節點，並
1被添加爲每個節點和它的直接子都標
2被添加爲每個節點和它下面的整個樹都標
有N- 1個連接爲n個節點（這意味着它必須是一個帶有根的自行車樹）

對不對？

首先找到根：不是任何連接結束的節點，即。 1在你的例子中。
然後檢查是否有其他連接沒有根作爲開始。
如果是，答案是2，否則1.沒有其他可能的值。
時間複雜度O（n）。