題目描述
在X森林里，上帝創建了生命之樹。
他給每棵樹的每個節點(葉子也稱為一個節點)上，都標了一個整數，代表這個點的和諧值。
上帝要在這棵樹內選出一個非空節點集S，使得對于S中的任意兩個點a,b，都存在一個點列 {a, v1, v2, …, vk, b}
使得這個點列中的每個點都是S里面的元素，且序列中相鄰兩個點間有一條邊相連。
在這個前提下，上帝要使得S中的點所對應的整數的和盡量大。
這個最大的和就是上帝給生命之樹的評分。
經過atm的努力，他已經知道了上帝給每棵樹上每個節點上的整數。
但是由于 atm 不擅長計算，他不知道怎樣有效的求評分。
他需要你為他寫一個程序來計算一棵樹的分數。

輸入
第一行一個整數 n 表示這棵樹有 n 個節點。(0<n<=10^5)
第二行 n 個整數，依次表示每個節點的評分。(每個節點的評分不超過10^6)
接下來 n-1 行，每行 2 個整數 u, v，表示存在一條 u 到 v 的邊。
由于這是一棵樹，所以是不存在環的。
輸出
輸出一行一個數，表示上帝給這棵樹的分數。
樣例輸入
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5
樣例輸出
8

解題思路：
https://blog.csdn.net/CrazyMooo/article/details/109080562

代碼如下：

#include <iostream> #include <vector> using namespace std; typedef long long LL; const int N = 100010; LL w[N]; LL ans;//開LL，不然會爆 vector<LL>T[N];void dfs(LL root, LL fa) {for (int i = 0; i < T[root].size(); i++) {int child = T[root][i];if (child == fa)continue;dfs(child, root);if (w[child] > 0)w[root] += w[child];}ans = max(ans, w[root]); }int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> w[i];}for (int i = 1; i <= n - 1; i++) {int a, b;cin >> a >> b;T[a].push_back(b);T[b].push_back(a);}dfs(1, -1);cout << ans << endl;return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[蓝桥杯2015初赛]生命之树-求树的最大子树权值和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。