CF526B Om Nom and Dark Park 题解

题目链接：CF526B Om Nom and Dark Park

题意：给定 \(2^{n+1}-1\) 个结点的满二叉树，求保证根到每一个叶子节点的路径权值和相等的情况下，增加权值的最小值

显然不能从根节点开始修改权值，不然也不知道改成什么才行

因此主要思路是从叶子结点向上修改权值，直到根结点为止

方便起见，用 a[x]表示结点 \(x\) 到它的父结点的那条边的权值

下文中提到的路径长指一个结点到它叶子结点的最终的距离

可以发现，对于一个待修改结点 \(x\) ，假设我们已经知道了它的左右子结点的路径长ls,rs（已经被修改了的路径长，因为是从叶子结点向上修改的）

则结点 \(x\) 到左子结点修改前的路径长为a[2*x]+ls，同理右子结点a[2*x+1]+rs

保证根到叶子节点路径权值和相等，因此要把上面这两个路径长中较小的那个补成较大的那个，这样花费肯定是最小的，又保证了以这个结点为根的子树满足题目要求

于是从下往上传递，过程中统计答案

时间复杂度 \(O(2^n)\)

主要代码很短

#define MAXN (int)(2e6+5)
int n,ans,a[MAXN],MX;
int dfs(int x)
{
	if(x>MX)return 0;
	int ls=dfs(x<<1),rs=dfs(x<<1|1);
	ans+=abs(ls+a[x<<1]-rs-a[x<<1|1]); // 每次修改的花费
	return max(a[x<<1]+ls,a[x<<1|1]+rs);
}
signed main()
{
	read(n);MX=(1<<(n+1))-1;
	for(int i=2; i<=MX; i++)
		read(a[i]);
	dfs(1);write(ans);
	return 0;
}

题外话

这题面好可爱 qwq