[数据结构与算法]满二叉树等长路径

满二叉树等长路径

给定一个深度为 n 的满二叉树，其 2ⁿ⁺¹?1 个顶点的编号为 1～2ⁿ⁺¹?1。

树的根节点为 1 号节点，除根节点外，第 i 号节点的父节点为第 ?i2? 号节点。

例如，当 n=3 时，二叉树如下所示：

树中每条边的长度已知，由此可以得到根节点到 2ⁿ 个叶节点的距离。

为了使得根节点到每个叶节点的距离都相等，我们可以进行任意次增边操作。

每次操作可以选择任意一条边，将其增加任意正整数长度。

我们希望在达成目的的同时，所有边的总增加长度尽可能小。

请你计算并输出总增加长度的最小可能值。

输入格式
第一行包含整数 n。

第二行包含 2ⁿ⁺¹?2 个整数 a2,a3,…,a²ⁿ⁺¹?1，其中 ai 表示第 i 号节点与第 ?i2? 号节点之间的边的长度。

输出格式
一个整数，表示总增加长度的最小可能值。

数据范围
前三个测试点满足 1≤n≤2。
所有测试点满足 1≤n≤10，1≤ai≤100。

输入样例

2
1 2 3 4 5 6

输出样例

5

思路：

自底向上遍历，两两比较

代码

#include<iostream>
#include<cmath>

using namespace std;
const int N = 3000;
int m, n, k, t, res, ans, sum, a[N], d[N];

int main() {
    cin >> n;
    m = pow(2, n + 1) - 1;
    k = pow(2, n);
    for (int i = 2; i <= m; ++i) {
        cin >> a[i];
        d[i] = a[i] + d[i >> 1];
    }

    for (int i = m; i > 1; i -= 2) {
        d[i - 1 >> 1] = max(d[i], d[i - 1]);
        res += abs(d[i] - d[i - 1]);
    }
    cout << res << endl;
    return 0;
}