洛谷 P1122 分析（别看）

科技起源的小号1

2026-10-15 20:36:56

发布于：天津

0阅读

0回复

0点赞

本题和P8625唯一不同的点只有P8625允许选空集而本题不允许

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

1.2 题目背景、允许、禁止与限制

一株奇怪的花卉，上面共连有 $n$ 朵花，共有 $n-1$ 条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数。所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。经过一系列“修剪”之后，还剩下最后一株花（也可能是一朵）。通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。
限制：
“美丽指数”有可能为负数
剩下的花朵不可以为空

1.3 题目数据范围与猜测

$1 \le n \le 10^5 \longrightarrow O(n)$

1.4 一句话概括题意

有一棵 $n$ 个节点 $m$ 条边树，选择其中一棵子树（什么也不选不是“一棵子树”）使得这棵子树中所有点的权值之和最大

2 题目破题推导

2.1 第一步：分情况讨论

考虑任意一个节点 $u$ 的贡献来源

第一部分是它本身的权值 $a_u$
第二部分是来自它对应所有子树的总权值
也就是对于每个子节点 $v$
若 $v$ 的总贡献 $f_v\ge0$ ，那么这个子分支就要选上，能增加总权值
若 $v$ 的总贡献 $f_v<0$ ，那么这个子分支选了反而是负担，那么就不选，相当于选 $0$

2.2 第二步：边界思想

这题很显然发现不能选择空集
那么结束的时候就不能像P8625那样将最大值与 $0$ 再取最大值

3 模型匹配

关键词：从下向上递推，动态求取最大值 $\longrightarrow$ $\huge{树型动态规划}$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std; 
#define int long long

int n;
const int N = 1e5 + 10;
int a[N];
int dp[N];
vector<int> g[N];
void dfs(int u, int fa){
    dp[u] = a[u];
    for (int now : g[u]){
        if (fa == now){
            continue;
        }
        dfs(now, u);
        dp[u] += max(dp[now], 1LL * 0);
    }
}

signed main(){
	
	cin >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
	}
	for (int i = 1;i < n;i++){
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, -1);
	int mx = INT_MIN;
	for (int i = 1;i <= n;i++){
		mx = max(mx, dp[i]);
	}
	cout << max(mx, 1LL * 0);
	
	return 0;
}