【動態規劃】cf1034C. Region Separation

?質因數分解套路的復雜度分析的動態規劃

題目大意

有一顆$n$個節點有點權的樹，初始整棵樹為$1$號區域，要求滿足下列規則：

• 除非$i$是最后一個等級，否則每一個$i$級區域都要被分成至少兩個$i+1$級區域
• 對于每種等級，每個點必須恰好屬于一個區域
• 一個區域的點集必須是連通的
• 對于相同等級，每個區域必須擁有相同的點權和

問有多少種合法的劃分方案，$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_k=k]$了。因此處理$f_k$的復雜度是$O(n\ln n)$。

接下去考慮dp計算把整棵樹分為若干個$i$級區域的方案數$g_i$。