专栏文章

P11363 [NOIP2024] 树的遍历题解（个人学习笔记）

sshaun2000
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minkbzye
此快照首次捕获于
2025/12/02 03:49
3 个月前
此快照最后确认于
2025/12/02 03:49
3 个月前
查看原文
一颗新树所有可能的根节点一定为一条从叶子到叶子的链 一条链的方案数为
∏(di−1)!(不在链上)∗∏(di−2)(在链上) \prod(d_i-1)!(不在链上)*\prod(d_i-2)(在链上)
在LCA处统计答案
fi,0/1f_{i,0/1} 表示是否包含被标记的边
在最初把阶乘提出
ans+=(invdi−1∗(fv,0∗fu,1+fv,1∗(fu,0+fu,1))) ans+=(inv_{d_i-1}*( f_{v,0}*f_{u,1} +f_{v,1}*(f_{u,0}+f_{u,1}) ))
(fu,0+=fv,0)∗=∏(di−1)!(f_{u,0}+=f_{v,0}) *= \prod(d_i-1)!
(fu,1+=fv,1)∗=∏(di−1)!(f_{u,1}+=f_{v,1})*=\prod(d_i-1)!
ans∗=∏(di−1)!ans*=\prod(d_i-1)!
特判 n=2

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...