洛谷P1122《最大子树和》

二月 16, 2019 2323

ProjectDP - 35

最简单的树形DP问题

题目描述

小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。于是当日课后，小明就向老师提出了这个问题：

一株奇怪的花卉，上面共连有N N朵花，共有N-1N−1条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。

老师想了一会儿，给出了正解。小明见问题被轻易攻破，相当不爽，于是又拿来问你。

输入输出格式

输入格式

第一行一个整数N(1 ≤ N ≤ 16000)。表示原始的那株花卉上共N朵花。

第二行有N个整数，第I个整数表示第I朵花的美丽指数。

接下来N-1行每行两个整数a,b，表示存在一条连接第a朵花和第b朵花的枝条。

输出格式

一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过2147483647。

输入输出样例

输入样例#1

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

输出样例#1：

1
3

说明

【数据规模与约定】

对于60%的数据，有N≤1000；

对于100%的数据，有N≤16000。

解题思路

只需要一维

设 f[i] 表示以 i 为根的子树的最大值

初始化： f[i] 为结点 i 的权值

转移：

f[u] = f[u] + max(f[v], 0)

其中 v 是 u 的儿子

答案： f 数组的最大值

简单吧！

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//
//  35.cpp
//  ProjectDP
//
//  Created by HandwerSTD on 2019/2/16.
//  Copyright © 2019 Handwer STD. All rights reserved.
//

#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 100000 + 10;

std::vector<int> head[MAXN];
int flower[MAXN], dp[MAXN], n, id[MAXN], ans;

/*
 *
 * dp[u] += std::max(0, dp[v]);
 *
 */

void DFS(int u, int fa) {
    dp[u] = flower[u];
    for (std::vector<int>::iterator it = head[u].begin(); it != head[u].end(); it++) {
        if ((*it) == fa) continue;
        DFS((*it), u);
        dp[u] += std::max(0, dp[(*it)]);
    }
    ans = std::max(ans, dp[u]);
}

int main(int argc, const char * argv[]) {
    std::ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> flower[i];
    for (int i = 1; i <= n - 1; ++i) {
        int prev = 0, next = 0;
        cin >> prev >> next;
        if (prev > next) std::swap(prev, next);
        head[prev].push_back(next);
        head[next].push_back(prev);
        ++id[next];
    }
    int root = 0;
    for (root = 1; root <= n; ++root)
        if (id[root] == 0) break;
    DFS(root, 0);
    cout << ans << endl;
    return 0;
}