NOIP提高組模拟 樹上摩托

Description

Sherco是一位經驗豐富的魔♂法師。Sherco在第零次聖杯戰争中取得了勝利,并取得了王之寶藏——王の樹。他想把這棵樹砍去任意條邊，拆成若幹棵新樹，并裝飾在他的摩托上，讓他的摩托更加酷炫。但Sherco認為，這樣生成的樹不具有美感，于是Sherco想讓每棵新樹的節點數相同。他想知道有多少種方法分割這棵樹。

Data Constraint

對于40%的資料，N ≤ 15（N表示節點數）

對于60%的資料，N ≤ 10^5

對于100%的資料，N ≤ 10^6

資料規模非常大，請使用高效的讀入方式。

Solution

我們枚舉每棵新樹的節點數，因為每棵新樹的節點數相同，是以節點數必須為N的約數。我們發現，設現在每棵新樹的節點數為x，對于一棵以i為根的樹，假設i有兩個兒子l,r，對于一次合法的分割，假如i和其中一個兒子l同屬于一個塊，這個塊的數量一定為kx（k!=0），而另一個兒子在另一個塊的話，那個塊的數量也一定為px(p!=0),那麼假如我們改變分割方案，讓i和另一個兒子r在一個塊，l獨自一個塊，那麼這時塊的數量就為kx-1和px+1，這顯然不是x的倍數，是以不可行。綜上所述，我們會發現對于一個固定的每棵新樹的節點數，最多隻有一個合法的分割方案。

知道這些後就很好做了。我們統計每個點以他為根的樹的數量記為size。枚舉每棵新樹的節點數x，統計有多少個點的size為x的倍數。若數量剛好為N/x，那麼則是一次合法的分割。

代碼

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=;
int first[maxn],last[maxn],next[maxn],n,i,t,j,k,l,x,y,num,ans;
int size[maxn],bz[maxn],v[maxn],fa[maxn];
bool bz1[maxn];
void lian(int x,int y){
    last[++num]=y;next[num]=first[x];first[x]=num;
}
int main(){
//  freopen("data.in","r",stdin);
    scanf("%d",&n);
    for (i=;i<n;i++){
        scanf("%d%d",&x,&y);
        lian(x,y);lian(y,x);
    }
    for (i=;i<=n;i++) size[i]=;
    v[]=;i=;j=;bz1[]=true;
    while (i<j){
        i++;
        for (t=first[v[i]];t;t=next[t]){
            if (bz1[last[t]]) continue;
            bz1[last[t]]=true;
            v[++j]=last[t];fa[last[t]]=v[i];
        }
    }
    for (i=j;i>=;i--){
        for (t=first[v[i]];t;t=next[t]){
            if (last[t]==fa[v[i]]) continue;
            size[v[i]]+=size[last[t]];
        }
    }
    for (i=;i<=n;i++)
        bz[size[i]]++;
    for (i=;i<=n;i++){
        if (n%i) continue;
        t=;
        for (j=;j<=n/i;j++)
            t+=bz[j*i];
        if (t==n/i) ans++;  
    }
    printf("%d\n",ans);
}