최대 합 경로 찾기(과제)

단말 노드 간의 최대 합을 찾는 문제

트리를 만든 후에, 후위 순회 하듯이 재귀를 통하여 문제를 해결한다

단말 노드 간의 최대 합을 찾는 방법 : https://junho0956.tistory.com/299?category=879042

 

#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;
}