Educational Codeforces Round 168 (Rated for Div. 2) D题

文章目录

• 题目来源
• • 题意
  • 思路
  • code

题目来源

D. Maximize the Root

题意

给定一棵n个点的数，根节点为1，每个点都有权值 a i a_i ai​
可以执行无限次操作：选择一个节点，将其子节点全部 − 1 -1 −1,自己的权值 + 1 +1 +1 (必须有子节点)
权值不能为负数，求根节点最大的权值

思路

考点：搜索+贪心

我们想让根节点的权值尽可能大，那么需要将除根节点外的最小权值尽可能变大
那么我们可以考虑dfs回溯的思想(或者用拓扑排序也可以)

从树的叶节点(树的末端)从后往前搜索
令mn为当前节点x的子节点的最小权值，那么当前节点的权值有2种可能：

• a x < m n a_x<mn ax​<mn 那么可以将 a x a_x ax​不断+1，将mn不断-1，这样可以使最小权值变大，直到操作为 a x = m n a_x=mn ax​=mn ,那么它最后的权值就为 ( a x + m n ) / 2 (a_x+mn)/2 (ax​+mn)/2，向下取整
• a x ≥ m n a_x≥mn ax​≥mn ,那么它可取到的最大权值就为 m n mn mn

当回溯到根节点1时，加上mn即可

code

const int N=1e6+5;
int a[N],b[N],fa[N];
vector<int> e[N];
void dfs(int x){
	int mn=1e10;
	for(auto y : e[x]){
		if(y==fa[x]) continue;//找到叶节点
		dfs(y);
		mn=min(mn,b[y]);//算出最小权值
	}
	if(mn==1e10){
		b[x]=a[x];
		return ;
	}
	if(x==1){
		a[1]+=mn;
		return ;
	}
	if(a[x]<mn) b[x]=(a[x]+mn)/2;
	else b[x]=mn;
}
void solve(){
	int n;cin >> n;
	for(int i=1;i<=n;++i){
		cin >> a[i];
		e[i].clear();
		b[i]=0; 
	}
	for(int i=2;i<=n;++i){
		cin >> fa[i];
		e[fa[i]].push_back(i);
		e[i].push_back(fa[i]);
	}
	dfs(1);
	cout << a[1] << endl;
	return ;
}