微信第三方做网站需要费用吗,网站开发保密协议范本下载,凡客诚品是什么,住房和城乡建设部网站造价师A. 树与路径 首先考虑一个dp的方法#xff0c;对于这种链划分的题目#xff0c;有一个很重要的思想就是按照每个点的角度考虑#xff0c;实际上链划分就是匹配问题#xff0c;每个点只能出一条边和入一条边#xff0c;所以我们拆点之后就是匹配#xff0c;这也是网络流最…A. 树与路径 首先考虑一个dp的方法对于这种链划分的题目有一个很重要的思想就是按照每个点的角度考虑实际上链划分就是匹配问题每个点只能出一条边和入一条边所以我们拆点之后就是匹配这也是网络流最少链覆盖的思路。
这道题是在树上那么就有更好的性质实际上对于每个点的状态就是将所连接的边进行匹配并且每个点的状态是独立的所以我们可以考虑一个暴力的dpdpi,jdp_{i,j}dpi,j表示的是i这个点包含父亲边划分为j条链的方案数然后可以得到转移如果没有链经过i那么直接相乘否则假设有k条链经过则需要乘上一个系数 (2kdui)(2k−1)!!\binom{2k}{du_i}(2k-1)!! (dui2k)(2k−1)!! 意义为选择2k个点进行匹配然后2n个点的完美匹配个数为(2n-1)!!这是一个经典结论具体可以通过枚举1号点的匹配递推出来。 fn(n−1)fn−2f_n(n-1)f_{n-2} fn(n−1)fn−2
然后由于整个问题每个点都是独立的并且可以看出这也是一个背包问题所以我们可以利用多项式求解。直接在将上面的系数看作是关于k的多项式然后乘起来最终的系数就是答案。
