判定转状态+序列问题上树形dp：0909T3

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132796834

考虑没有括号怎么做。

对于这类+*表达式求值问题，正常思考的dp是状态 $O(n)$ ，总共为 $O(n^2)$ 的

但其实可以对于每个dp记录两个值，分别为答案dp，和后面的乘积和g

如果接乘号，就是 $[j](dp,g)\to[j](dp+g(i-1),gi)$

之所以要-1，是因为g我们在之前的dp已经囊括了

接加号， $[j](dp,g)\to[j+1](dp+i,i)$

然后考虑有括号，显然可以建一个括号树，然后类似树形dp的过程。只不过j的转移不一样而已

令当前所有情况答案为dp，所有情况最后的乘积和为g就行了

for(j=0; j<=w[u]; ++j) for(k=0; k<=w[v]; ++k) {
	Mod(dps[j+k+1], dp[u][j]*C[w[v]][k]%mo+dp[v][k]*C[w[u]][j]%mo); 
	Mod(gs[j+k+1], dp[v][k]*C[w[u]][j]%mo); 
	Mod(dps[j+k], (dp[u][j]-g[j])*C[w[v]][k]%mo+g[j]*dp[v][k]%mo); 
	Mod(gs[j+k], g[j]*dp[v][k]%mo); 
}

其实可以写成矩阵形式来转移