2015年第六届蓝桥杯省赛-J. 生命之树

2021-12-16 · 114次阅读 · 原创 · 数据结构与算法

原题链接

题面

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

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

上帝要在这棵树内选出一个非空节点集 S，使得对于 S 中的任意两个点 a,b，都存在一个点列 $\{a, v_1, v_2, \cdots, v_k, b\}$ 使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点间有一条边相连。

在这个前提下，上帝要使得 S 中的点所对应的整数的和尽量大。

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

经过 atm 的努力，他已经知道了上帝给每棵树上每个节点上的整数。但是由于 atm 不擅长计算，他不知道怎样有效的求评分。他需要你为他写一个程序来计算一棵树的分数。

输入描述

第一行一个整数 n 表示这棵树有 n 个节点。

第二行 n 个整数，依次表示每个节点的评分。

接下来 n-1 行，每行 2 个整数 u, v，表示存在一条 u 到 v 的边。由于这是一棵树，所以是不存在环的。

其中， $0 < n \leq 10^5$ , 每个节点的评分的绝对值不超过 10⁶。

输出描述

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

输入样例

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

输出样例

题解

树形DP，图论

题目要求即从一个连通图中找到一个连通子图，且该连通子图的节点权值和最大。

每个节点只有两种状态，可以用 f[i][1] 表示节点 i 要取，f[i][0] 表示节点 i 不取，那么影响节点 i 的只有它的孩子节点 j 了，动态转移方程：

$f[i][1] = \sum_{\text{j为i的子节点}}(max(0, f[j][1])) \\ f[i][0] = \max_{\text{j为i的子节点}}(max(f[j][0], f[j][1]))$

最后只要在f[1][1] 和 f[1][0]中找到最大的那个就是这棵树的分数了。

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, a[N];
vector<int> g[N];
long long f[N][2];
bool v[N];

void dp(int p) {
    v[p] = true;
    f[p][1] = a[p];
//    f[p][0] = 0;
    for (int &y:g[p]) {
        if (v[y]) continue;
        dp(y);
        f[p][0] = max(f[p][0], max(f[y][0], f[y][1]));  //不选节点p
        f[p][1] = max(f[p][1], f[p][1] + f[y][1]);      //选节点p
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dp(1);
    cout << max(f[1][0], f[1][1]) << endl;

    return 0;
}

标题：	2015年第六届蓝桥杯省赛-J. 生命之树
链接：	https://www.fightingok.cn/detail/179
更新：	2022-09-18 22:45:51
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可