Untitled

#include <bits/stdc++.h>

using namespace std;
string s;
long long int pos, total, num;
int ans, MaxSum;

typedef struct Node {
    Node *left, *right;
    int data;
}node;
node* makenode(int a, int negative){
    node* newnode = new node;
    if(negative == 1) newnode->data = -a;
    else newnode->data = a;
    total += newnode->data;
    newnode->left = newnode->right = NULL;
    return newnode;
}
node* buildTree(){
    node *tmp = NULL;
    int val;
    if(s[pos] == '('){
        pos++;
        int negative;
        if(s[pos] == '-'){
           negative = 1;
           pos++;
           val = s[pos]-'0';
           pos++;
           while(s[pos] >= '0' && s[pos] <='9'){
                val = val*10+s[pos]-'0';
                pos++;
            }
            tmp = makenode(val, negative);
            tmp->left = buildTree();
            pos++;
            tmp->right = buildTree();
            pos++;
        }
        else if(s[pos] >= '0' && s[pos] <='9'){
            negative = 0;
            val = s[pos]-'0';
            pos++;
            while(s[pos] >= '0' && s[pos] <='9'){
                val = val*10+s[pos]-'0';
                pos++;
            }
            tmp = makenode(val, negative);
            tmp->left = buildTree();
            pos++;
            tmp->right = buildTree();
            pos++;
        }
        else if(s[pos] == ')') return NULL;
    }
    return tmp;
}
void print_pre(node* root){
    if(root != NULL){
        cout << root->data << " ";
        print_pre(root->left);
        print_pre(root->right);
    }
}
void print_in(node* root){
    if(root != NULL){
        print_in(root->left);
        cout << root->data << " ";
        print_in(root->right);
    }
}
void print_post(node* root){
    if(root != NULL){
        print_post(root->left);
        print_post(root->right);
        cout << root->data << " ";
    }
}
void Find(node* root, int& M, int curSum){
    if(root == NULL) return;
    curSum += root->data;
    if(root->left == NULL && root->right == NULL && curSum > M)
        M = curSum;
    Find(root->left, M, curSum);
    Find(root->right, M, curSum);
}
int FindMaxPathSum(node* root){
    if(root == NULL) return 0;
    MaxSum = INT_MIN;
    Find(root, MaxSum, 0);
    return MaxSum;
}
// 0: protected
// 1: no tower and not protected
// 2: tower
int dfs(node* root){
    if(root == NULL) return 0;
    int l = dfs(root->left), r = dfs(root->right);
    if(l==1 || r==1){
        num++;
        return 2;
    }
    if(l==2 || r==2) return 0;
    else return 1;
}
int BinaryTower(node* root){
    if(root == NULL) return 0;
    if(dfs(root) == 1) num++;
    return num;
}
node* DeleteLeaf(node* root){
    if(root == NULL) return NULL;
    if(root->left == NULL && root->right == NULL){
        total -= root->data;
        delete root;
        return NULL;
    }
    root->left = DeleteLeaf(root->left);
    root->right = DeleteLeaf(root->right);
    return root;
}
bool check(node* a, node* b){
    if(a == NULL && b == NULL) return true;
    if(a == NULL || b == NULL) return false;
    return (check(a->left, b->right) && check(a->right, b->left));
}
bool Foldable(node* root){
    if(root == NULL) return true;
    return check(root->left, root->right);
}
node* Invert(node* root){
    if(root == NULL) return NULL;
    node *tmp = root->left;
    root->left = Invert(root->right);
    root->right = Invert(tmp);
    return root;
}
int Search(node* root, int& path){
    if(root == NULL) return 0;
    int l = Search(root->left, path), r = Search(root->right, path);
    int curLeft, curRight;
    curLeft = curRight = 0;
    if(root->left != NULL && root->left->data == root->data)
        curLeft = l + 1;
    if(root->right != NULL && root->right->data == root->data)
        curRight = r + 1;
    path = max(path, curLeft+curRight);
    return max(curLeft, curRight);
}
int UnitedPath(node* root){
    ans = 0;
    Search(root, ans);
    return ans;
}
int main(void){
    string cmd;
    while(cin >> s){
        pos = total = 0;
        node* root = buildTree();
        while(cin >> cmd){
            if(cmd == "Traverse"){
                print_pre(root);
                cout << endl;
                print_in(root);
                cout << endl;
                print_post(root);
                cout << endl;
            }
            else if(cmd == "WeightSum") cout << total << endl;
            else if(cmd == "MaximumPathSum") cout << FindMaxPathSum(root) << endl;
            else if(cmd == "BinaryTower"){
                num = 0;
                cout << BinaryTower(root) << endl;
            }
            else if(cmd == "Foldable"){
                int ok = Foldable(root);
                if(ok) cout << "Yes" << endl;
                else cout << "No" << endl;
            }
            else if(cmd == "KingdomUnitedPath") cout << UnitedPath(root) << endl;
            else if(cmd == "DeleteLeaf") root = DeleteLeaf(root);
            else if(cmd == "Invert") root = Invert(root);
            else if(cmd == "End"){
                cout << endl;
                break;
            }
        }
    }
    return 0;
}