蓝桥杯2015年第六届真题-生命之树-题解（C++代码）

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

int n;

const int MaxN = 1e5;

long long w[MaxN + 1];//每个点的权重

long long ans;

vector<int> g[MaxN + 1];//邻接表

//以root为根，算出最大的权和

void dfs(int root, int fa) {

   for (int i = 0; i < g[root].size(); ++i) {

       int son = g[root][i];//其中一个孩子

       if (son != fa) {

           dfs(son, root);

           if (w[son] > 0) {

               w[root] += w[son];

           }

       }

   }

   if (w[root] > ans) {

       ans = w[root];

   }

}

int main() {

   ios_base::sync_with_stdio(false);

   cin.tie(NULL);

   cin >> n;

   for (int i = 1; i <= n; ++i) {

       cin >> w[i];

   }

   for (int j = 0; j < n - 1; ++j) {

       int u, v;

       cin >> u >> v;

       g[u].push_back(v);

       g[v].push_back(u);

   }

   dfs(1, 0);

   cout << ans << '\n';

   return 0;

}