題干：

在X森林里，上帝創建了生命之樹。

他給每棵樹的每個節點（葉子也稱為一個節點）上，都標了一個整數，代表這個點的和諧值。
上帝要在這棵樹內選出一個非空節點集S，使得對于S中的任意兩個點a,b，都存在一個點列 {a, v1, v2, ..., vk, b} 使得這個點列中的每個點都是S里面的元素，且序列中相鄰兩個點間有一條邊相連。

在這個前提下，上帝要使得S中的點所對應的整數的和盡量大。
這個最大的和就是上帝給生命之樹的評分。

經過atm的努力，他已經知道了上帝給每棵樹上每個節點上的整數。但是由于 atm 不擅長計算，他不知道怎樣有效的求評分。他需要你為他寫一個程序來計算一棵樹的分數。

「輸入格式」
第一行一個整數 n 表示這棵樹有 n 個節點。
第二行 n 個整數，依次表示每個節點的評分。
接下來 n-1 行，每行 2 個整數 u, v，表示存在一條 u 到 v 的邊。由于這是一棵樹，所以是不存在環的。

「輸出格式」
輸出一行一個數，表示上帝給這棵樹的分數。

「樣例輸入」
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5

「樣例輸出」
8

「數據范圍」
對于 30% 的數據，n <= 10
對于 100% 的數據，0 < n <= 10^5, 每個節點的評分的絕對值不超過 10^6 。

資源約定：
峰值內存消耗 < 256M
CPU消耗 ?< 3000ms

解題報告：

? 因為沒有試題鏈接，所以就假裝AC了。。。寫了一遍也沒檢查，可能有錯。

不知道是否AC的代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; ll val[MAX]; int n; vector<int> vv[MAX]; ll dp[MAX]; void dfs(int cur,int rt) {int up = vv[cur].size();dp[cur] = val[cur];for(int i = 0; i<up; i++) {int v = vv[cur][i];if(v == rt) continue;dfs(v,cur);if(dp[v] >= 0) dp[cur] += dp[v];} }int main() {cin>>n;for(int i = 1; i<=n; i++) {scanf("%lld",val+i);}for(int a,b,i = 1; i<=n-1; i++) {scanf("%d%d",&a,&b);vv[a].pb(b);vv[b].pb(a);}dfs(1,-1);ll ans = -999999999999;for(int i = 1; i<=n; i++) {ans = max(ans,dp[i]);}cout << ans;return 0 ; }

?

總結

以上是生活随笔為你收集整理的【蓝桥杯官网试题 - 真题训练】生命之树（树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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