ZJOI2022 树
考虑一下容斥，钦定若干个节点满足要么都为叶子，要么只有一遍是叶子，另一边无所谓。
记 \(dp_{i,j,k}\) 表示前 \(i\) 个节点， \(T_1\) 中有 \(j\) 个 \(1\to i-1\) 的节点不是叶子，\(T_2\) 中有 \(k\) 个 \(i+1\to n\) 的节点不是叶子的方案。
转移时：
-
\(T_1\) 中是叶子，\(T_2\) 中不是叶子
- 选择容斥 转移到 \(dp_{i,j,k}\) ，系数 \((-1)jk\)
- 不容斥 转移到 \(dp_{i,j,k-1}\) ，系数 \(j(k-1)\)
-
\(T_1\) 中不是叶子，\(T_2\) 中是叶子
-
选择容斥 转移到 \(dp_{i+1,j,k}\) ，系数 \((-1)jk\)
-
不选择容斥，转移到 \(dp_{i+1,j+1,k}\)，系数 \(jk\)
-
复杂度 \(O(n^3)\) 。
标签：系数,Redemption,容斥,Moon,叶子,jk,节点,dp From： https://www.cnblogs.com/jesoyizexry/p/17846370.html