Sherco是一位经验丰富的魔♂法师。

Sherco在第零次圣杯战争中取得了胜利,并取得了王之宝藏——王の树。

他想把这棵树砍去任意条边，拆成若干棵新树，并装饰在他的摩托上，让他的摩托更加酷炫。

但Sherco认为，这样生成的树不具有美感，于是Sherco想让每棵新树的节点数相同。

他想知道有多少种方法分割这棵树。

首先一个很显然的结论是，每块的大小一定是n的约数，对于一种块的大小，显然分法是唯一的

证明？口胡一下就是一个子树如果正好大小为k且根的父亲边没被断掉就肯定得不到答案

好了我们考虑枚举每一个约数让后dfs一次？

超时了！n<=10^6

我们考虑一下将原树看做一个有根树，一个节点可以作一个块的”根”，当且仅当该节点的 size 能被块的大小整除 预处理出每个节点的 size,枚举树的大小 k,判断 size 为 k 的倍数的节点数量是否为n/k就好了

复杂度nlgn，注意要打bfs

#pragma GCC opitmize("O3")#pragma G++ opitmize("O3")#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;struct edge{ int v,nt; }G[2000010]; queue
        
          q;int sz[1000010],h[1000010],n,cnt=0,A=0,c[1000010],f[1000010];inline void adj(int x,int y){	G[++cnt]=(edge){y,h[x]}; h[x]=cnt;	G[++cnt]=(edge){x,h[y]}; h[y]=cnt;}void bfs(){	q.push(1);	for(int x;!q.empty();q.pop()){		sz[c[++A]=x=q.front()]=1;		for(int i=h[x];i;i=G[i].nt)			if(!sz[G[i].v]) f[G[i].v]=x,q.push(G[i].v);	}	for(;A;--A) sz[f[c[A]]]+=sz[c[A]];}int main(){	scanf("%d",&n);	for(int x,y,i=1;i