[BOJ] 13325 - 이진 트리

[백준] 13325 - 이진 트리

간선에 값을 더해야 한다면 가장 공통되는 부모부터 값을 더하는 것이 가장 효율적이라는 것이 자명하다. 따라서 각 경로에 얼마의 값을 더해야 하는지 알고 있다면 각 구간에서 더해야 하는 최솟값을 더하고 아래 레벨로 탐색하면 된다.

1. dfs를 통해 루트부터 각 리프노드까지의 경로 상에 있는 간선의 가중치 합을 배열로 저장한다.
2. 저장된 가중치 합 배열을 탐색하며 가중치 합의 최대값에서 현재 값을 뺀 값을 최소값 세그먼트 트리에 업데이트 한다.
3. 만들어진 세그먼트 트리를 루트부터 dfs로 탐색하며 현재 노드의 값 - 현재까지 부모까지 더한 누적값을 전역변수 ans에 저장한다.

소스코드

#include <iostream>
#include <queue>
#include <functional>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;

int k, binarytree[(1 << 21) + 5], h = 1, present = 1, total = 0, maximum= 0;
vector<int> seg, arr;

// 최소 트리 만들고
void update(int idx, int n) {
	int idxIs = h + idx - 1;
	seg[idxIs] = n;
	while (idxIs > 1) {
		idxIs /= 2;
		seg[idxIs] = min(seg[idxIs * 2], seg[idxIs * 2 + 1]);
	}
}

// 합을 세그로 업데이트 해주는 과정
void dfs(int now, int sum, int lev) {
	if (lev == k) {
		arr.push_back(sum);
		maximum = max(maximum, sum);
		return;
	}
	dfs(now * 2, sum + binarytree[now * 2], lev+1);
	dfs(now * 2 + 1, sum + binarytree[now * 2 + 1], lev+1);
}

// 돌면서 부모의 값 누적해 넘겨주고 나에서 뺀값 더한다.
void dfs2(int now, int sum, int lev) {
	if (now >= h * 2) return;
	if (seg[now] - sum > 0) {
		total += seg[now] - sum;
		sum += seg[now] - sum;
	}
	dfs2(now * 2, sum, lev + 1);
	dfs2(now * 2 + 1, sum, lev + 1);
}

int main(void) {
	scanf("%d", &k);
	int n = (1 << (k + 1));
	while (n > h) h <<= 1;
	seg.resize(h * 2);
	for (int i = 2; i < n; i++) {
		scanf("%d", binarytree + i);
		total += binarytree[i];
	}

	dfs(1, 0, 0);

	for (int i = 0; i < arr.size(); i++) {
		update(i + 1, maximum - arr[i]);
	}

	dfs2(1, 0, 0);

	printf("%d", total);
	
	return 0;
}