蓝桥杯 9.生命之树

生命之树

原题目链接

题目描述

在 X 森林里，上帝创建了生命之树。

他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。

上帝要在这棵树内选出一个节点集 S，使得对于 S 中任意两个点 a, b，都存在一个点列：

a, v1, v2, …, vk, b

使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点之间有一条边相连。

在这个前提下，上帝希望 S 中所有节点的整数和尽量大。

这个最大的和就是上帝给生命之树的评分。

注意：集合 S 可以为空。

输入描述

• 第一行一个整数 n，表示这棵树有 n 个节点。
• 第二行 n 个整数，依次表示每个节点的评分。
• 接下来 n-1 行，每行两个整数 u, v，表示存在一条 u 到 v 的边。

保证：

• 1 <= n <= 100000
• 每个节点的评分的绝对值不超过 1000000

输出描述

输出一行一个整数，表示上帝给这棵树的最大评分。

输入输出样例

输入

5
1 -2 -3 4 5
4 2
3 1
1 2
2 5

输出

8

c++代码

#include<bits/stdc++.h>
#include<stdio.h>

using namespace std;

typedef long long ll;

ll n, a, b, ans = 0;
vector<ll> trees, dp, know;
vector<vector<ll>> edges;

void dfs(ll root) {
    know[root] = 0;
    dp[root] += trees[root];
    for (ll x : edges[root]) {
        if (!know[x]) continue;
        dfs(x);
        if (dp[x] > 0) dp[root] += dp[x];
    }
    ans = max(ans, dp[root]);
}

int main() {
    scanf("%lld", &n);
    edges = vector<vector<ll>>(n + 1);
    trees = vector<ll>(n + 1, 0), dp = vector<ll>(n + 1, 0), know = vector<ll>(n + 1, 1);
    for (ll i = 1; i <= n; i++) scanf("%lld", &trees[i]);
    for (ll i = 0; i < n - 1; i++) {
        scanf("%lld %lld", &a, &b);
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    dfs(1);
    cout << ans;
    return 0;
}//by wqs

思路解析

题目的意思就是要我们找一颗子树，使得这颗子树的权值和最大。