SS241126C. 树（tree）
题意
给你一个以 \(1\) 为根的树，每个点有点权 \(v_i\)。设这棵树的点集为 \(V\)，一个合法的子集 \(V' \subseteq V\)，满足存在 \(p \in V'\)，使得 \(V'\) 中任意两点的 LCA 都是 \(p\)。
把 \(V\) 分成若干个 \(V'\) 称为一种划分方案，一种划分方案 \(\{ V' \}\) 的价值为 \(\prod_{\{V'\}} (\sum_{i \in V'} v_i)\)。求所有合法发划分方案的价值和。答案对输入的 \(mod\) 取模。
\(n \le 100\)。
思路
黄队讲得非常仔细，可惜我太菜了。
不保证过程正确，如有误欢迎指出/bx
考虑刻画合法 \(V'\)。发现其形如有一个点 \(p\) 是 \(V'\) 中深度最浅的点，我们把它叫做集合的头，然后 \(p\) 的每棵子树里，可以选择至多 \(1\) 个点加入集合。
考虑先解决一个简单的问题，计算合法划分方案数。
考虑树形 DP，从下往上转移。要计算加入点 \(u\) 的贡献，分 \(u\) 是一个集合的头，或者是集合的一般结点来讨论。如果 \(u\) 是一个集合的头，那么 \(u\) 的每棵子树都可以选择一个或者不选点加入 \(u\) 的集合；如果 \(u\) 是一般结点，那么我们先不算贡献，把它的贡献留到处理头结点时去计算。
设 \(f_{u,s,0/1}\) 表示处理到点 \(u\)，点 \(u\) 的子树里一共有多少个一般结点未被使用，点 \(u\) 是/不是头结点，的划分方案数。答案是 \(f_{1,0,1}\)。
对于 \(u\) 是头结点的情况。枚举 \(u\) 的儿子 \(v\)，枚举 \(v\) 的子树有多少个未被使用的一般结点，枚举在 \(v\) 的子树中选择一个一般结点加入 \(u\) 的集合还是不选。
转移复杂度是 \(siz_u\)。注意枚举每个 \(v\) 要把上一个 \(v\) 时计算的 \(f_u\) 覆盖掉，注意转移顺序应该是 \(j\) 从大往小枚举。初始 \(f_{u,0,1}=1\)。
\[(v \in son_u) \\ \begin{aligned} f_{u,s+j,1} & \gets f_{u,s,1} \times f_{v,j}\\ f_{u,s+j-1,1} & \gets f_{u,s,1} \times j \times f_{v,j} \end{aligned} \]对于 \(u\) 是一般结点的情况，仍然枚举 \(u\) 的儿子 \(v\)，枚举 \(v\) 的子树有多少个没有被使用的一般结点。初始 \(f_{u,1,0}=1\)。
\[(v \in son_u)\\ f_{u,s+j+1,0} \gets f_{u,s,0} \times f_{v,j} \]应该是这样的吧。时间是 \(O(n^2)\)。
求原问题。
考虑展开那一坨连乘，相当于在每个集合里选择一个点涂黑，然后贡献是黑点点权的乘积，对每种涂色方案的贡献求和。即
\[\sum_{\{ V' \} } \sum_{\{col\}} \prod_{col_u = 1} v_u \]仍然考虑从下往上树形 DP。考虑加入点 \(u\) 带来的影响。
\[\begin{cases} u 是头结点 \begin{cases} col_u = 1 \Rightarrow [v 子树不选点/选一个白点]\\ col_u = 0 \Rightarrow [v 子树不选点/选一个点]\cup [至少一个 v 子树选择了黑点] \end{cases}\\ u 是一般结点 \begin{cases} \begin{rcases} col_u = 1 \\ col_u = 0 \end{rcases} 留到头结点再处理 \end{cases} \end{cases} \]设 \(f_{u,s_0,s_1,0/1}\) 表示子树 \(u\) 有 \(s_0\) 个未被使用的白点，有 \(s_1\) 个未被使用的黑点，点 \(u\) 是头结点，集合里有没有黑点，的方案的价值之和。\(g_{u,s_0,s_1}\) 表示 \(u\) 是一般结点的答案。
初值 \(f_{u,0,0,0}=1,f_{u,0,0,1}=v_u,g_{u,1,0}=1,g_{u,0,1}=v_u\)。
\[\begin{aligned} f_{u,s_0+x,s_1+y,1} & \gets f_{u,s_0,s_1,1} \times (f_{v,x,y}+g_{v,x,y})\\ f_{u,s_0+x-1,s_1+y,1} & \gets f_{u,s_0,s_1,1} \times (f_{v,x,y}+g_{v,x,y}) \times x\\ f_{u,s_0+x,s_1+y,0} & \gets f_{u,s_0,s_1,0} \times (f_{v,x,y}+g_{v,x,y})\\ f_{u,s_0+x-1,s_1+y,0} & \gets f_{u,s_0,s_1,0} \times (f_{v,x,y}+g_{v,x,y}) \times x\\ f_{u,s_0+x,s_1+y-1,1} & \gets f_{u,s_0,s_1,0} \times (f_{v,x,y}+g_{v,x,y}) \times y\\ g_{u,s_0+x,s_1+y} & \gets g_{u,s_0,s_1} \times (f_{v,x,y}+g_{v,x,y}) \end{aligned} \]应该就是这些了吧。
答案就是 \(f_{1,0,0,1}\)。
code
应该不会太难写。
标签：结点,SS241126C,tree,times,枚举,cases,gets,col From： https://www.cnblogs.com/liyixin0514/p/18571024