域名购买网站,高端的网站,泉州网站建设公司首选公司,做网站优化的注意事项质因数分解套路的复杂度分析的动态规划 题目大意 有一颗$n$个节点有点权的树#xff0c;初始整棵树为$1$号区域#xff0c;要求满足下列规则#xff1a; 除非$i$是最后一个等级#xff0c;否则每一个$i$级区域都要被分成至少两个$i1$级区域对于每种等级#xff0c;每个点必… 质因数分解套路的复杂度分析的动态规划 题目大意 有一颗$n$个节点有点权的树初始整棵树为$1$号区域要求满足下列规则 除非$i$是最后一个等级否则每一个$i$级区域都要被分成至少两个$i1$级区域对于每种等级每个点必须恰好属于一个区域一个区域的点集必须是连通的对于相同等级每个区域必须拥有相同的点权和问有多少种合法的划分方案$n \le 10^6,a_i \le 10^9$. 题目分析 首先考虑判断把树分为$k$个2级区域的合法性$f_k$记点权和为$tot$。 一种朴素的想法就是对于每一个$k$自底向上遍历整棵树若剩余子树大小恰好为$tot\over k$就割去这颗子树如果整棵树能够被处理完$k$就是合法的。每次判定复杂度为$O(n)$. 注意到这个想法里每次割去子树的大小$s_i$恰好是$tot\over k$的倍数并且不难发现$k$合法的充要条件就是恰有$k$个$s_i≡0(\text{mod }\frac{tot}{k})$。简短解释一下对于一颗$s_i≡0(\text{mod }\frac{tot}{k})$的子树由于它的所有子树都奉行割去$s_j≡0(\text{mod }\frac{tot}{k})$的原则那么剩下的包括点$i$的连通块就是$i$子树内最小的$\ge {tot\over k}$的连通块。因此$\sum [s_k≡0(\text{mod }\frac{tot}{k})] \le k$并且当且仅当$k$时合法。 有了这个性质考虑如何统计$f_k$。容易发现对于合法的$k$$\frac{tot}{k}$的任意约数$k$都是合法的。而对于子树$s_i$其最小有贡献的$k\frac{tot}{\text{gcd}(s_i,tot)}$。所以这里只需要对每个$s_i$存下最小的合法$k$再以质因数分解题的套路处理一遍就能算出$[f_kk]$了。因此处理$f_k$的复杂度是$O(n\ln n)$。 接下去考虑dp计算把整棵树分为若干个$i$级区域的方案数$g_i$。转载于:https://www.cnblogs.com/antiquality/p/10692714.html
