题目描述

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n;
LL f[N];
int w[N];
int h[N], e[N * 2], ne[N * 2], idx;

//开始的时候想麻烦了，以为要换根。
//我以为 以点k为根 的子树，f[k]只能向下表示，不能像上表示，所以每个点都要当作根节点跑一边。
//其实不用， 假设 点k 他父节点那部分的权值和大于子节点那部分的权值和， 那么最终的答案一定不在点 k 上产生，
//它父节点那部分 必定有一个点 能表示权值的最大值，否则， k的子树就是权值和的最大值。

//半吊子DP还是要好好完善一下。

void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

//第二个参数是记录父节点，防止向回走
void dfs(int u,int fa){
    f[u] = w[u];

    for (int p = h[u] ; p != -1 ; p = ne[p]){
        int j = e[p];
        if (j != fa){
            dfs(j, u);
            f[u] += max(0ll, f[j]);
        }
    }
}



int main(){
    //读入
    cin >> n;
    for (int i = 1 ; i <= n ; i ++) cin >> w[i];
    memset(h, -1, sizeof h);
    for (int i = 0 ; i < n - 1 ; i ++){
        int a, b;
        cin >> a >> b;
        add(a, b);add(b, a);//无向图
    }

    //树形DP
    dfs(1, -1);

    LL res = -1e10;
    for (int i = 1 ; i <= n ; i ++) res = max(res, f[i]);

    cout << res << endl;
    return 0;
}