nthuoj_11208_max_path.cpp

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

using namespace std;

int str2int(const string& s)
{
    stringstream ss;
    int x;
    ss.str(s);
    ss >> x;
    return x;
}

int main()
{
    string in;

    while (getline(cin, in)) {
        stringstream in_ss, item_ss;
        vector<int> list;
        string item;

        in_ss.str(in);
        list.push_back(0); // let tree root begin from index 1
        while (getline(in_ss, item, ' ')) {
            list.push_back(str2int(item));
        }

        stack<int> index_st, value_st;
        index_st.push(1);
        value_st.push(0);

        int max_path_weight = 0;
        while (!index_st.empty()) {
            int i = index_st.top();
            int v = value_st.top() + list[i];
            index_st.pop(); value_st.pop();

            if (2*i < list.size()) {
                // preorder: push right then push left
                index_st.push(2*i+1);
                value_st.push(v);
                index_st.push(2*i);
                value_st.push(v);
            } else {
                // termination: arrive leaf
                max_path_weight = max(max_path_weight, v);
            }
        }
        cout << max_path_weight << endl;
        in.clear();
    }

    return 0;
}