Submission

Score: 100

User: Shangbin

Problemset: composite tree

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-11 11:39:27

#include <bits/stdc++.h>
using namespace std;

string a, b, result;
vector<int> sumtree(2e6);

string LeftBranch(string str){
    string res;
    stack<char> s;
    int start = 0;
    while (str[start] != '(') start++;
    s.push('(');
    for (int i = start + 1; i < str.length(); i++){
        if (str[i] == '(') s.push('(');
        if (str[i] == ')') s.pop();
        if (s.size() == 0) break;
        res += str[i];
    }
    return res;
}
string RightBranch(string str){
    string res;
    stack<char> s;
    int start = 0;
    while (str[start] != '(') start++;
    s.push('(');
    while (s.size() > 0){
        start++;
        if (str[start] == '(') s.push('(');
        if (str[start] == ')') s.pop();
    }
    s.push('(');
    for (int i = start + 2; i < str.length(); i++){
        if (str[i] == '(') s.push('(');
        if (str[i] == ')') s.pop();
        if (s.size() == 0) break;
        res += str[i];
    }
    return res;
}
void branch(string str1, string str2, int i){
    if (str1.length() == 0 || str2.length() == 0) return;
    sumtree[i] = (str1[0] - '0') + (str2[0] - '0');
    branch(LeftBranch(str1), LeftBranch(str2), 2*i);
    branch(RightBranch(str1), RightBranch(str2), 2*i + 1);
}
void dfs(int i){
    if (sumtree[i] == 0) return;
    result += to_string(sumtree[i]);
    result += '(';
    dfs(2*i);
    result += ')';
    result += '(';
    dfs(2*i + 1);
    result += ')';
    
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> a >> b;
    branch(a, b, 1);
    dfs(1);
    // for (int i = 0; i < (1 << 4); i++){
    //     cout << sumtree[i] << ' ';
    // }
    cout << result;
}