Codeforces Gym 102565E. OneZeroTree | Alpha1022's Blog
Opened this issue · 0 comments
Alpha1022 commented
https://www.alpha1022.me/articles/cf-gym-102565e.htm
写这个套路题只是为了练手 / 借机会整改一下大多项式模板。 直接考虑点分治。 对于当前的一棵子树，考虑求出 (f_i) 表示这棵子树的根往下延伸的所有路径中，费用等于 (i) 的方案数。 考虑怎么求这个。首先 DFS 求出 (g_i) 表示这棵子树的根往下延伸的所有路径中，长度为 (i) 的条数。 那么有 [ f_i = \sum\limits_{j=i}^{n-1} \bino