网站首页
编程语言
数据库
系统相关
其他分享
编程问答
Shrinking
2024-07-28
CF1060F Shrinking Tree
考虑分别以每个点为根计算概率,可以计算所有边固定了收缩顺序的概率之和后除以\((n-1)!\)即为答案设\(f_{x,i}\)表示在\(x\)的子树内,删除最后\(i\)条边前后根的编号不发生变化的概率和,所求即为\(f_{rt,n-1}\)记当前点为\(v\),父节点为\(u\),因为收缩\((u,v)\)时,之前的