nthuoj_11208_max_path_recursive.cpp

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

int max_path_weight(const vector<int>& tree, int index)
{
    if (index*2 >= tree.size()) {
        // termination: arrive leaf
        return tree[index];
    }
    return tree[index] + max(
            max_path_weight(tree, index*2),
            max_path_weight(tree, index*2+1)
            );
}

int main()
{
    string in;

    while (getline(cin, in)) {
        stringstream in_ss;
        vector<int> tree;
        int node;

        in_ss.str(in);
        tree.push_back(0); // let tree root begin from index 1
        while (in_ss >> node) {
            tree.push_back(node);
        }
        cout << max_path_weight(tree, 1) << endl;
        in.clear();
    }

    return 0;
}