Description

小Y最近從同學那里聽說了一個十分牛B的高級數據結構——塊狀樹。聽說這種數據結構能在sqrt(N)的時間內維護樹上的各種信息，十分的高效。當然，無聊的小Y對這種事情毫無興趣，只是對把樹分塊這個操作感到十分好奇。他想，假如能把一棵樹分成幾塊，使得每個塊中的點數都相同該有多優美啊！小Y很想知道，能有幾種分割方法使得一棵樹變得優美。小Y每次會畫出一棵樹，但由于手速太快，有時候小Y畫出來的樹會異常地龐大，令小Y感到十分的苦惱。但是小Y實在是太想知道答案了，于是他找到了你，一個天才的程序員，來幫助他完成這件事。

Input

第一行一個正整數N，表示這棵樹的結點總數，接下來N-1行，每行兩個數字X，Y表示編號為X的結點與編號為Y的結點相連。結點編號的范圍為1-N且編號兩兩不同。

Output

一行一個整數Ans，表示所求的方案數。

Sample Input

6
1 2
2 3
2 4
4 5
5 6

Sample Output

3

HINT

100%的數據滿足N<=1000000。

Solution

我竟然天真的以為$2e8$能跑過去直到我被最大的點卡到$10s$……

感覺也說不上什么算法，就算他是亂搞吧。

一開始洲哥給了一個$n\sqrt{n}$的寫法。下一段根號做法可以不看因為我感覺我寫的可能比正解還難懂……

我們先枚舉當前要分的塊大小$k$，再隨便找一個根$DFS$一下，從下往上貪心的分，也就是夠$k$個就分成一塊。感性理解一下還是非常正確的……對于每個點$x$我們求出$(\sum size[son[x]]\%k)+1$，如果存在某個點的這個值大于$k$的話顯然就是不合法的。其中$size[son[x]]\%k$也就是$son[x]$這顆子樹里面分完了剩下的點。這個為什么是對的我就不多說了……要真想不懂的話可以直接去看下面正解做法。

其實仔細想想，確定了塊大小$k$之后，那么每一塊內的根的$size$肯定就是$k$的倍數。這個應該還是比較顯然的，因為你是從下往上貪心來分的。那么我們直接開個桶記下$size$，對于每一個能被$n$整除的塊大小$k$，統計有多少$size[x]$被$k$整除，如果與$n/k$相同則合法。復雜度應該是$O(n+\sqrt{n}logn)$

Code

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #define N (1000009) 5 using namespace std; 6 7 struct Edge{int to,next;}edge[N<<1]; 8 int n,ans,size[N],u,v,Keg[N]; 9 int head[N],num_edge; 10 11 inline int read() 12 { 13 int x=0; char c=getchar(); 14 while (c<'0' || c>'9') c=getchar(); 15 while (c>='0' && c<='9') x=x*10+c-'0', c=getchar(); 16 return x; 17 } 18 19 void add(int u,int v) 20 { 21 edge[++num_edge].to=v; 22 edge[num_edge].next=head[u]; 23 head[u]=num_edge; 24 } 25 26 void DFS(int x,int fa) 27 { 28 size[x]=1; 29 for (int i=head[x]; i; i=edge[i].next) 30 if (edge[i].to!=fa) 31 { 32 DFS(edge[i].to,x); 33 size[x]+=size[edge[i].to]; 34 } 35 Keg[size[x]]++; 36 } 37 38 int main() 39 { 40 n=read(); 41 for (int i=1; i<=n-1; ++i) 42 { 43 u=read(); v=read(); 44 add(u,v); add(v,u); 45 } 46 DFS(1,0); 47 for (int i=1; i<=n; ++i) 48 if (n%i==0) 49 { 50 int sum=0; 51 for (int j=1; i*j<=n; ++j) 52 sum+=Keg[i*j]; 53 ans+=(sum==n/i); 54 } 55 printf("%d\n",ans); 56 }

轉載于:https://www.cnblogs.com/refun/p/10219614.html

總結

以上是生活随笔為你收集整理的BZOJ4401:块的计数(乱搞)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。