백준 13325 이진 트리
#include <iostream>
#include <vector>
#include <cstring>
#include <math.h>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 2097152 + 5;
int k, n;
vector<pair<ull, ull>> edge (MAXN, make_pair(0,0));
int visited[MAXN];
ull toLeaf[MAXN] = { 0 };
ull getToLeaf(int curnode) {
visited[curnode] = 1;
ull maxdist = 0;
if ((curnode * 2 <= n) && (visited[curnode * 2] == 0)) {
if (edge[curnode].first > 0)
maxdist = max(maxdist, edge[curnode].first + getToLeaf(curnode * 2));
}
if ((curnode * 2 + 1 <= n) && (visited[curnode * 2 + 1] == 0)) {
if (edge[curnode].second > 0)
maxdist = max(maxdist, edge[curnode].second + getToLeaf(curnode * 2 + 1));
}
toLeaf[curnode] = maxdist;
return maxdist;
}
void addWeight(int curnode, int maxdist) {
visited[curnode] = 1;
if ((curnode * 2 <= n) && (visited[curnode * 2] == 0)) {
if (edge[curnode].first > 0) {
edge[curnode].first = (maxdist - toLeaf[curnode * 2]);
addWeight(curnode * 2, maxdist - edge[curnode].first);
}
}
if ((curnode * 2 + 1 <= n) && (visited[curnode * 2 + 1] == 0)) {
if (edge[curnode].second > 0) {
edge[curnode].second = (maxdist - toLeaf[curnode * 2 + 1]);
addWeight(curnode * 2 + 1, maxdist - edge[curnode].second);
}
}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> k;
n = pow(2, k + 1) - 1;
for (int i = 1; i <= n - pow(2, k); ++i) {
int w1, w2;
cin >> w1 >> w2;
edge[i] = make_pair(w1, w2);
}
memset(visited, 0, sizeof(visited));
getToLeaf(1);
memset(visited, 0, sizeof(visited));
addWeight(1, toLeaf[1]);
ull sum = 0;
for (int i = 1; i <= n; ++i) {
sum += edge[i].first;
sum += edge[i].second;
}
cout << sum;
return 0;
}