演算法訓練 結點選擇
提交此題 評測記錄
資源限制
時間限制:1.0s 記憶體限制:256.0MB
問題描述
有一棵 n 個節點的樹,樹上每個節點都有一個正整數權值。如果一個點被選擇了,那么在樹上和它相鄰的點都不能被選擇。求選出的點的權值和最大是多少?
輸入格式
第一行包含一個整數 n 。
接下來的一行包含 n 個正整數,第 i 個正整數代表點 i 的權值。
接下來一共 n-1 行,每行描述樹上的一條邊。
輸出格式
輸出一個整數,代表選出的點的權值和的最大值。
樣例輸入
5
1 2 3 4 5
1 2
1 3
2 4
2 5
樣例輸出
12
樣例說明
選擇3、4、5號點,權值和為 3+4+5 = 12 。
資料規模與約定
對于20%的資料, n <= 20。
對于50%的資料, n <= 1000。
對于100%的資料, n <= 100000。
權值均為不超過1000的正整數。
轉載請註明出處,本文鏈接:https://www.uj5u.com/houduan/19199.html
標籤:C語言
上一篇:c++編譯報錯,求大佬康康我!
