輸入:

7 -1 -1 -1 1 1 1 0 1 4 2 5 3 6 4 7 5 7 6 7

輸出:

3

代碼如下:

#include <iostream> #include <vector> using namespace std; const int N = 100010; typedef long long LL; LL ans; vector<LL>t[N]; LL w[N];void dfs(int root, int 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);//假設節點1為根節點，沒有父節點，用-1表示cout << ans << endl;return 0; }

總結

以上是生活随笔為你收集整理的洛谷 P1122 最大子树和-求树的最大子树权值和的全部內容，希望文章能夠幫你解決所遇到的問題。

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