洛谷 P1352 分析（别看）

科技起源的小号1

2026-10-15 21:52:29

发布于：天津

2阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

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

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

背景：
有一棵有根树，每个点有一个快乐指数 $r_i$
允许：
对于某个点，若其直接上司参与了活动，它就一定不会参与，否则可以选择参与或不参与
总快乐指数为所有参与活动点的最大值总和，请最大化这个总快乐指数
限制：
有根

1.3 题目数据范围与猜测

$1 \le n \le 6\times10^3 \longrightarrow O(n^2)$

1.4 一句话概括题意

有一棵有根树，求在某些选点限制下最大化点权总和

2 题目破题推导

2.1 第一步：分情况讨论

每个点 $u$ 只有两种可能性

$u$ 参与活动
那对于所有 $E=(u,v)$ ， $v$ 都应该是不选择的状态
$u$ 不参与活动
那对于所有 $E=(u,v)$ ， $v$ 选择或不选择都满足条件

3 模型匹配

关键词：树形结构，动态求取最小值 $\longrightarrow$ $\huge{树形dp（背包问题）}$

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

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

int n;
const int N = 6e3 + 10;
int a[N];
vector<int> g[N];
int dp[N][2];// dp[i][0]代表不选这个点的最大得分，dp[i][1]代表选这个点的最大得分 
bool has_father[N];
void dfs(int u, int fa){
	dp[u][0] = 0, dp[u][1] = a[u];
	for (int now : g[u]){
		if (now == fa){
			continue;
		}
		dfs(now, u);
		dp[u][1] += dp[now][0];
		dp[u][0] += max(dp[now][1], dp[now][0]);
	}
} 

int main(){
	
	cin >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
	}
	for (int i = 1;i < n;i++){
		int l, k;
		cin >> l >> k;
		g[l].push_back(k);
		g[k].push_back(l);
		has_father[l] = true;
	}
	int root = 1;
	for (int i = 1;i <= n;i++){
		if (has_father[i]){
			root = i;
			break;
		}
	}
	dfs(root, -1);
	cout << max(dp[root][0], dp[root][1]);
	
	return 0;
}