树哈希板子题，本题解中默认已经进行了树哈希。

我们找出所有子树大小之和为 $N-M$ 的子树，只有这样的子树可能成为答案。

然后考虑一个非常暴力的做法：对于每一棵这样的子树（记为 a），我们爆搜出 a 所有的子树，并计算出 a 的每种子树需要在原树中出现多少次。具体的，对于每一棵 a 的子树，设这棵子树（记为 b）的根节点到 a 的根节点的路径上的结点数为 $x$，那么我们就要求 b 在原树中出现 $x$ 次（形状相同的子树的需要次数直接相加）。这是因为 b 上方的子树都会包含 b，如果不这样统计的话 b 上方的子树也会对 b 的判断产生影响。

至于为什么这样复杂度就是对的：我们考虑父节点的子树大小之和严格大于子节点的子树大小之和。因此，任意两个子树大小之和为 $N-M$ 的子树一定不交，所以这些子树的大小之和是 $O(N)$ 的。

如果哪里没有明白可以看代码。

#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
#define int long long
struct edge{
	int to,next;
}e[maxn<<1];
int n,m,h[maxn],tot,hs[maxn],sz[maxn],sum[maxn];
unordered_map<int,int> m1,m2;
unordered_set<int> ans;
void addedge(int u,int v){
	e[++tot].to=v;
	e[tot].next=h[u];
	h[u]=tot;
	return;
}
int xs(int x){
	x^=11;
	x^=(x<<9);
	x^=(x>>4);
	x^=(x<<5);
	x^=14;
	return x;
}
void dfs1(int x,int fa){//求出所有子树的大小、子树大小和 和 哈希值
	sz[x]=1;
	hs[x]=45;
	for(int i=h[x];i;i=e[i].next){
		if(e[i].to==fa){
			continue;
		}
		dfs1(e[i].to,x);
		hs[x]+=xs(hs[e[i].to]);
		sz[x]+=sz[e[i].to];
		sum[x]+=sum[e[i].to]; 
	}
	sum[x]+=sz[x];
	m1[hs[x]]++;
	return; 
}
void dfs2(int x,int fa,int dep){//求出每种子树需要出现次数
	for(int i=h[x];i;i=e[i].next){
		if(e[i].to==fa){
			continue;
		}
		dfs2(e[i].to,x,dep+1);
	}
	m2[hs[x]]+=dep;
	return; 
}
void check(int x,int fa){
	m2.clear();
	dfs2(x,fa,1);
	for(unordered_map<int,int>::iterator it=m2.begin();it!=m2.end();it++){
		if(m1[it->first]<m2[it->first]){
			return;
		}
	}
	ans.insert(hs[x]);
	return;
}
void dfs3(int x,int fa){//找出所有满足子树大小之和为 N-M 的子树
	for(int i=h[x];i;i=e[i].next){
		if(e[i].to==fa){
			continue;
		}
		dfs3(e[i].to,x);
	}
	if(n-sum[x]==m){
		check(x,fa);
	}
	return; 
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		addedge(u,v);
		addedge(v,u);
	}
	dfs1(1,0);
	dfs3(1,0);
	cout<<ans.size();
	return 0;
}