https://www.myijk.com/p/2775

#黄，#贪心

题意：

• 给定一棵以 1 为根的树，每一个节点有一个权值。
• 选择一个点集，需要满足点集中至多只有一对兄弟。
• 求点集的权值之和最大值和最小值。

看到题目，你可能会想到树形 dp。但是转移实在是太复杂了。我们有更简单的贪心做法。

以求解权值之和的最大值为例。

• 注意到，一个节点的所有儿子中至少可以选择一个。所以对于所有的节点，选择儿子中的最大正权值（如果没有则不选）。
• 然后可以选择一个点，与点集中的点组成兄弟。我们也令其最大，也就是所有儿子集合中的次大取最大。

题目就这样结束了，非常简单。

再看一下实现吧。

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, fa[N], val[N];
vector<int> val_son[N];
int main(){
	cin >> n;
	for(int i = 2; i <= n; i ++){
		cin >> fa[i];
	}
	for(int i = 1; i <= n; i ++){
		cin >> val[i];
		val_son[fa[i]].pb(val[i]);
	}
	ll ans = 0, add = 0;
	for(int i = 0; i <= n; i ++){
		sort(val_son[i].begin(), val_son[i].end(), greater<int>());
		int m = (int)val_son[i].size();
		if(m){
			if(val_son[i][0] > 0){
				ans += 1ll*val_son[i][0];
				if(m >= 2 && val_son[i][1] > 0) add = max(add, 1ll*val_son[i][1]);
			}
		}
	}
	cout << ans + add << " ";
	ans = 0, add = 0;
	for(int i = 0; i <= n; i ++){
		int m = (int)val_son[i].size();
		if(m){
			if(val_son[i][m-1] < 0){
				ans += 1ll*val_son[i][m-1];
				if(m >= 2 && val_son[i][m-2] < 0) add = min(add, 1ll*val_son[i][m-2]);
			}
		}
	}
	cout << ans + add;
	return 0;
}