P11363 [NOIP2024] 树的遍历题解（个人学习笔记）
shaun2000
·
·
题解
一颗新树所有可能的根节点一定为一条从叶子到叶子的链
一条链的方案数为
\prod(d_i-1)!(不在链上)*\prod(d_i-2)(在链上)
在LCA处统计答案
在最初把阶乘提出
$ ans+=(inv_{d_i-1}*( f_{v,0}*f_{u,1} +f_{v,1}*(f_{u,0}+f_{u,1}) ))
(f_{u,0}+=f_{v,0}) *= \prod(d_i-1)!
(f_{u,1}+=f_{v,1})*=\prod(d_i-1)!
ans*=\prod(d_i-1)!
特判 n=2