题目分析

首先注意到答案构成一个连续值域区间。考虑扔到表达式树上，对每个子树考虑完之后推出当前节点。

我们规定有值的节点是 $0$ 类，取较小值是 $-1$，较大值是 $1$。

对于 $0$ 类节点，最小、最大显然都是 $1$。

考虑 $-1$ 类节点的最小值，你可以把较大的数全部扔到一个子树中，另一个子树就可以保持原有的值，所以两者取较小即可（同时我们一定可以通过调整，把一个点扔走来构造大一点的值）；考虑最大值，我们希望两者较小值最大，那就尽量平均，两边都可以淘汰掉一定量据此可以推出式子。

考虑 $1$ 类节点最大值，可以把小的值扔到一棵树，另一棵树继承最大值即可，两者取较大；最小值的话肯定两个子树都用最小来平摊，这样最小是两者的和，不然一定有一个更大，一个更小。

这样就可以递推出来根的最大最小了。

时间复杂度 $O(n)$。

代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e7+1;
int n,rt,val[N][2];
string s;
struct TreeNode{
    int type,ls,rs,siz;
}f[N];
int build(int start,const string&command,int&cur){
    cur=(++n);
    if(command[start]=='?'){
        f[cur].type=0,f[cur].siz=1;
        do start++;
        while(start<command.size()&&(command[start]==','||command[start]==')'));
        return start;
    }
    if(command[start+1]=='i')
        f[cur].type=-1;
    else
        f[cur].type=1;
    int ret=build(build(start+4,command,f[cur].ls),command,f[cur].rs);
    f[cur].siz=f[f[cur].ls].siz+f[f[cur].rs].siz;
    return ret;
}
void dfs(int u){
    if(!f[u].type){
        val[u][0]=val[u][1]=1;
        return;
    }
    dfs(f[u].ls),dfs(f[u].rs);
    if(f[u].type>0)
        val[u][1]=max(val[f[u].ls][1]+f[f[u].rs].siz,f[f[u].ls].siz+val[f[u].rs][1]),
        val[u][0]=val[f[u].ls][0]+val[f[u].rs][0];                                                
    else
        val[u][1]=val[f[u].ls][1]+val[f[u].rs][1]-1,
        val[u][0]=min(val[f[u].ls][0],val[f[u].rs][0]);
    return;
}
int main(){
    cin>>s;
    build(0,s,rt);
    dfs(rt);
    cout<<val[rt][1]-val[rt][0]+1;
    return 0;
}