단말 노드 간의 최대 합을 찾는 문제
트리를 만든 후에, 후위 순회 하듯이 재귀를 통하여 문제를 해결한다
단말 노드 간의 최대 합을 찾는 방법 : https://junho0956.tistory.com/299?category=879042
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
struct tree {
long long w;
tree* parent = NULL;
tree* left = NULL;
tree* right = NULL;
};
struct pii {
long long l, r;
};
tree* left_tree(int l, int r, int idx);
tree* right_tree(int l, int r, int idx);
int tree_size;
int order[100001];
tree node[100001];
tree* root;
long long answer;
int max_node;
tree* right_tree(int l, int r, int idx) {
return left_tree(l, r, idx);
}
tree* left_tree(int l, int r, int idx) {
if (!(l <= r && idx < tree_size)) return NULL;
tree* now = &node[order[idx]];
if (l == r) return now;
int next = order[idx];
now->left = left_tree(l, next - 1, idx + 1);
now->right = right_tree(next + 1, r, idx + (next - l) + 1);
if (now->left != NULL) now->left->parent = now;
if (now->right != NULL) now->right->parent = now;
return now;
}
void make_tree() {
root = &node[order[0]];
root->left = left_tree(0, order[0] - 1, 1);
root->right = right_tree(order[0] + 1, tree_size - 1, order[0] + 1);
if (root->left != NULL) root->left->parent = root;
if (root->right != NULL) root->right->parent = root;
}
void init() {
cin >> tree_size;
for (int i = 0; i < tree_size; i++) cin >> node[i].w, node[i].left = node[i].right = node[i].parent = NULL;
for (int i = 0; i < tree_size; i++) cin >> order[i];
}
pii searching(tree* now) {
if (now->left == NULL && now->right == NULL) {
answer = max(answer, now->w);
return { now->w, now->w };
}
pii ret, L, R;
if (now->left != NULL && now->right != NULL) {
L = searching(now->left);
R = searching(now->right);
if (L.l >= R.l) ret.l = now->w + L.l;
else ret.l = now->w + R.l;
ret.r = now->w + L.l + R.l;
answer = max(answer, ret.r);
}
else if (now->left != NULL && now->right == NULL) {
L = searching(now->left);
ret.l = ret.r = now->w + L.l;
}
else if (now->right != NULL && now->left == NULL) {
R = searching(now->right);
ret.l = ret.r = now->w + R.l;
}
return ret;
}
void solve() {
answer = -987654321;
pii ret = searching(root);
answer = max(answer, ret.r);
cout << answer << "\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc;
cin >> tc;
while (tc--) {
init();
make_tree();
solve();
}
return 0;
}
|
'algorithm' 카테고리의 다른 글
| 의료봉사(과제) (0) | 2020.04.27 |
|---|---|
| convex hull (0) | 2020.04.07 |
