題目

Sherco是一位經驗豐富的魔♂法師。
Sherco在第零次圣杯戰爭中取得了勝利,并取得了王之寶藏——王の樹。
他想把這棵樹砍去任意條邊，拆成若干棵新樹，并裝飾在他的摩托上，讓他的摩托更加酷炫。
但Sherco認為，這樣生成的樹不具有美感，于是Sherco想讓每棵新樹的節點數相同。
他想知道有多少種方法分割這棵樹。
樣例輸入：
第一行一個正整數N，表示這棵樹的結點總數。
接下來N-1行，每行兩個數字X，Y表示編號為X的結點與編號為Y的結點相連。結點編號的范圍為[1,N]。
6
1 2
2 3
2 4
4 5
5 6

樣例輸出：
一個整數，表示方案數。注意，不砍去任何一條邊也算作一種方案。
3

數據范圍：
對于40%的數據，N ≤ 15
對于60%的數據，N ≤ 10^5
對于100%的數據，N ≤ 10^6
數據規模非常大，請使用高效的讀入方式。

---

剖解題目

。。。。。

---

思路

只知道和n的約數有關。。。。。

---

解法

40%：暴力枚舉刪哪些邊。
60%：搞一搞可以知道一些性質。
1.樹的大小只可能是n的約數。
2.樹的大小確定后，如果有分割方案只可能有一種。
所以直接枚舉樹的大小，dfs判斷即可。時間O(nn√)
100%:繼續找性質。
發現，如果一個節點可以作為一塊的根，那么以這個節點為根的子樹的size一定能被塊的大小整除。
預處理出所有節點size，枚舉樹的大小k，如果size為k的倍數的節點數的大小是n/k的話，便是合法方案，加入答案。時間O(nlogn)。
然而，如果用dfs弄會爆棧，所以用bfs吧（好難搞QwQ）

---

代碼

#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++)using namespace std;const int maxn=1000005; int n,num,ans; int fre[maxn*2],next[maxn*2],go[maxn*2],size[maxn],T[maxn*2],dad[maxn]; bool bz[maxn],b[maxn];void add(int x,int y) {go[++num]=y;next[num]=fre[x];fre[x]=num; } int main() { // freopen("T.in","r",stdin);scanf("%d",&n);fo(i,1,n-1){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}int h=0,t=1,hh=0,tt=0;T[1]=1;bool bo;while (h!=t){int u=T[++h];b[u]=true;int i=fre[u];while (i){if (b[go[i]]) {i=next[i];continue;}T[++t]=go[i];dad[go[i]]=u;i=next[i];}}h=1; t++;while (t!=h){int u=T[--t];size[u]++;int i=fre[u];while (i){if (go[i]==dad[u]) size[go[i]]+=size[u];i=next[i];}}ans=1;fo(i,2,n/2)if (n%i==0){int t=0;fo(j,1,n) if (size[j]%i==0) ++t;if (t==n/i) ++ans;}if (n!=1) printf("%d",ans+1);else printf("1"); }

總結

以上是生活随笔為你收集整理的树上摩托【NOIP2016提高A组模拟9.4】的全部內容，希望文章能夠幫你解決所遇到的問題。

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