思路
仔细理解一下题意可以发现。
对于每个完整的括号序列都是独立的，然后就想到分治。高度是序列中所有括号序列的最大值，宽度是所有括号序列宽度和\(+1\)。
然后仔细想了一下，这种分治应该是可以被卡成\(n^2\)的。
题解就比较厉害了。
其实基本思想和分治相似。
建立一棵树的模型。每到一个左括号就给当前节点添加一个子节点。每到一个右括号，就回到父亲节点。
等到建完这张图，发现其实就是把分治的过程给提前处理出来了。
然后对于这棵树\(dp\)一下就好了。
当前节点的高度是孩子中最大高度\(+1\)，宽度是孩子宽度之和\(+1\)，答案就是宽度\(\times\)高度\(-\)孩子的答案之和
代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<vector>
using namespace std;
typedef long long ll;
#define int ll
const int N = 500000 + 100;
vector<int>e[N];
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
char s[N];
int w[N],h[N];
int dfs(int u) {
int k = e[u].size();
w[u] = 1;
h[u] = 0;
int sum = 0;
for(int i = 0;i < k;++i) {
int v = e[u][i];
sum += dfs(v);
w[u] += w[v] + 1;
h[u] = max(h[u],h[v]);
}
h[u]++;
return !u ? sum : w[u] * h[u] - sum;
}
int fa[N];
signed main() {
int T = read();
while(T--) {
scanf("%s",s + 1);
int now = 0,tot = 0;
memset(fa,0,sizeof(fa));
int n = strlen(s + 1);
for(int i = 1;i <= n;++i) {
if(s[i] == '(') e[now].push_back(++tot),fa[tot] = now,now = tot;
else now = fa[now];
}
printf("%lld\n",dfs(0));
for(int i = 0;i <= tot;++i) e[i].clear();
}
return 0;
}