90pts表达式树 TLE on#10求调悬2关

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5,MOD=10007;
int N,len=0,flag=1;
string s,tmp="";
struct Node{
	string value;
	int Left,Right;
	void Build(){
		value="";
		Left=-1,Right=-1; 
	}
	void Build(string val){
		value=val;
		Left=-1,Right=-1;
	}
}Tree[MAXN];
int poskh(int l,int r){
	int t=0;
	for(int i=l;i<=r;i++){
		if(s[i]=='(')t++;
		if(s[i]==')')t--;
		if(t==0)return i;
	}
	return -1;
}
string isval(int l,int r){
	if(l==r&&s[l]=='_')return "_";
	return "";
}
int findlow(int l,int r){
	int t=0,k=-1;
	for(int i=r;i>=l;i--){
		if(s[i]=='_')continue;
		if(s[i]=='(')t++;
		if(s[i]==')')t--;
		if(s[i]=='+'&&t==0)return i;
		if(s[i]=='*'&&t==0&&k==-1)k=i;
	}
	return k;
}
int BuildTree(int l,int r){
	if(l>r)return -1;
	string tmp=isval(l,r);
	if(tmp!=""){
		Tree[len].Build(tmp);
		return len++;
	}
	if(s[l]=='('&&poskh(l,r)==r)return BuildTree(l+1,r-1);
	int p=findlow(l,r);
	if(p==-1)return -1;
	Tree[len].Build(string(1,s[p]));
    int root=len++;
    Tree[root].Left=BuildTree(l,p-1);
    Tree[root].Right=BuildTree(p+1,r);
    return root;
}
pair<int,int> DFS(int u){
	if(u==-1)return make_pair(0,0);
	if(Tree[u].value=="_")return make_pair(1,1);
	pair<int,int>t1=DFS(Tree[u].Left),t2=DFS(Tree[u].Right);
    int L1=t1.first,L2=t1.second;
    int R1=t2.first,R2=t2.second;
    int cnt0=0,cnt1=0;
    if(Tree[u].value=="+"){
        cnt0=(L1*R1)%MOD;
        cnt1=(L1*R2%MOD+L2*R1%MOD+L2*R2%MOD)%MOD;
    }else if(Tree[u].value=="*"){
        cnt0=(L1*R1%MOD+L1*R2%MOD+L2*R1%MOD)%MOD;
        cnt1=(L2*R2)%MOD;
    }
    return make_pair(cnt0,cnt1);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>N>>s;
	for(int i=0;i<N;i++){
		if(flag&&s[i]!='(')tmp+='_',flag=0;
		tmp+=s[i];
		if(s[i]=='(')flag=1;
		else if(s[i]==')')flag=0;
		else if(s[i]=='+'||s[i]=='*')flag=1;
	}
	if(flag)tmp+='_';s=tmp;
	int root=BuildTree(0,s.size()-1);
	cout<<DFS(root).first%MOD;
	
	return 0;
}