111A

https://ac.nowcoder.com/acm/contest/111/A

（好像经常会忽略加粗字体）

其实看到加粗字体，知道形成方式后就很显然了。不一定知道是树形dp，但肯定知道要递归，高度和宽度就会操作了。

由于相接的两部分反色，于是要算和当前同色的面积，只要当前总面积减去一层递归下的面积和即可。

#include<bits/stdc++.h>
using namespace std;
long long sum[410100],w[401000],h[400010];
char s[401010];
long long read(){
	char ch=getchar();long long x=0,f=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
long long dfs(long long x){
	long long res=0,i=x+1;
	w[x]=1;h[x]=1;
	for(i=x+1;s[i]!=')';){
		long long ne=dfs(i);
		res+=sum[i];
		h[x]=max(h[x],h[i]+1);
		w[x]+=w[i]+1;
		i=ne;
	}
	sum[x]=h[x]*w[x]-res;
	return i+1;
}
void work(){
	scanf("%s",s+1);
	memset(sum,0,sizeof(sum));
	memset(h,0,sizeof(h));
	memset(w,0,sizeof(w));
	long long ans=0;
	for(long long i=1;s[i];){
		long long ne=dfs(i);
		ans+=sum[i];
		i=ne;
	}
	printf("%lld\n",ans);
}
int main(){
	int t=read();
	while(t--){
		work();
	}
	return 0;
}