题意

求由所有长度为 $2n$2n的合法括号匹配序列组成字典树的二分图最大匹配（给边染色是的染色的边没有交点）

做法

考虑树形 $dp$dp(可能不是?).
$dp\left[i\right]\left[j\right]\left[0/1\right]$dp[i][j][0/1]表示当前节点已经有 $i$i个左括号， $j$j个右括号, 且改节点与父亲节点的边是否染色 $\left(0/1\right)$(0/1)的方案数
则有转移方程:
$dp\left[i\right]\left[j\right]\left[0\right]=dp\left[i\right][j-1]\left[1\right](j\>i)+dp[i-1]\left[j\right]\left[1\right]$dp[i][j][0]=dp[i][j−1][1](j>i)+dp[i−1][j][1]
$dp\left[i\right]\left[j\right]\left[1\right]=max\left(dp\right[i-1\left]\right[j\left]\right[0]+1+dp[i\left]\right[j-1\left]\right[1],dp[i-1\left]\right[j\left]\right[1]+1+dp[i\left]\right[j-1\left]\right[0\left]\right)$dp[i][j][1]=max(dp[i−1][j][0]+1+dp[i][j−1][1],dp[i−1][j][1]+1+dp[i][j−1][0])
答案为 $dp\left[n\right]\left[n\right]\left[1\right]$dp[n][n][1], 总状态数 $O\left(n^2\right)$O(n2), 转移 $O\left(1\right)$O(1), 总复杂度 $O\left(n^2\right)$O(n2).
但由于转移涉及到大小比较，所以需要用大数，实际不用大数也能过，不知道原因(可能 $dp\left[i\right]\left[j\right]\left[0\right]$dp[i][j][0]与 $dp\left[i\right]\left[j\right]\left[1\right]$dp[i][j][1]比较接近,而且没有等于1e9+7的情况)

代码

python3太慢（提速技巧: 交pypy3(可提速3倍)，尽量少开多维数组，少定义局部变量）

n = int(input())
f = [[0]*(n+1) for i in range(n+1)]
g = [[0]*(n+1) for i in range(n+1)]
mod = 10**9+7
for i in range(1, n + 1):
    f[0][i] = g[0][i - 1]
    g[0][i] = f[0][i - 1] + 1
t = [0, 0]
for i in range(1, n + 1):
    for j in range(i, n + 1):
        if i > 0:
            f[i][j] += g[i - 1][j]
            t[0] = g[i - 1][j]
            t[1] = f[i - 1][j] + 1
        if j > i:
            f[i][j] += g[i][j-1]
            t[0] += f[i][j - 1] + 1
            t[1] += g[i][j - 1]
        for k in t: g[i][j] = max(g[i][j], k)
print(g[n][n]%mod)