在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 。

---

題目分析：題意一開始沒讀懂，去問的zx學長，簡單來說就是從樹中求一個最大連通子塊，保證這個連通子塊的權值和最大，因為說子樹不太合適，就叫做連通子塊啦

題目給到了1e5的數據，所以暴力是肯定不能考慮的了，因為涉及到權值和的問題，所以我們不難聯想到前綴和，在樹上維護前綴和不就是樹形dp嘛，但如果是單純的維護前綴和的話，又不太好更新答案，所以我們考慮一下如何設計dp

想了半天還是沒有思路啊，但zx學長看了一眼就給秒掉了，再次不得不承認人與人之間的差距。。

這個題目給出的是一棵無根樹，我們依然可以當做有根樹來做，隨意找一個節點當做根，跑一遍dfs，dp[i]代表節點i為上邊界的子連通塊的最大值，因為是子連通塊而不是子樹，所以在任意節點我們是可以直接斷開的，為什么要斷開呢？因為假如節點i的某棵子樹做出的貢獻是負數，那么我們完全可以舍棄掉這棵子樹，從而使得每次轉移的答案最優，這樣轉移方程也就很容易了：

dp[u]=max(dp[v],0);v為u的所有子節點

維護完dp后O(n)跑一遍最大值就是答案啦

這里需要注意一下，一開始我理解的dp[i]的含義有誤，所以導致整個思路混亂，從而沒有正確的設計出轉移方程，我一開始以為dp[i]代表的是到節點i為止，子連通塊中的最大值，從而出現了另一個疑問：如果最大值是在沿著節點i的父節點那條鏈上該怎么辦呢？其實并不用擔心這個問題，如果包含最大值的那一坨真的出現在節點i父節點的那條鏈上，雖然我們不能用節點i來更新最大值，但總有節點是可以更新到這個最大值的，我們可以這樣理解，節點i作為最大值這一坨的下界，自然無法更新答案，但只要是這個最大值合法，那么他必定存在一個上界，也是屬于這棵樹中的任意一個節點，當遍歷到上界的這個節點的時候，就可以更新相應的最大值了，所以在這里個人認為dp[i]理解為以節點i為上界的最大子連通塊比較合適

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;vector<int>node[N];LL dp[N];int val[N];void dfs(int u,int f) {dp[u]=val[u];for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==f)continue;dfs(v,u);dp[u]+=max(dp[v],0LL);//狀態轉移方程} }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",val+i);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);node[x].push_back(y);node[y].push_back(x);}dfs(1,-1);LL ans=-inf;for(int i=1;i<=n;i++)ans=max(ans,dp[i]);printf("%d\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的蓝桥杯 - 生命之树(树形dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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