#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+7;
int n;
inline int read()
{
	int X=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){X=(X<<1)+(X<<3)+ch-'0';ch=getchar();}
	return X;
}
vector<int> G[N],D[N];
int siz[N],son[N],vis[N],dep[N],dis[N][30];
void findroot(int x,int pre,int tot,int &root)
{
	siz[x]=1;son[x]=0;
	for(int y:G[x])if(y!=pre&&!vis[y])
	{
		findroot(y,x,tot,root);
		siz[x]+=siz[y];
		son[x]=max(son[x],siz[y]);
	}
	son[x]=max(son[x],tot-siz[x]);
	if(!root||son[x]<son[root])root=x;
}
int fa[N];
void extend(int x,int pre,int d,int r)
{
	siz[x]=1;
	while((int)D[r].size()<=d)D[r].push_back(0);D[r][d]++;
	dis[x][dep[r]]=d;
	for(int y:G[x])if(y!=pre&&!vis[y])
	{
		extend(y,x,d+1,r);
		siz[x]+=siz[y];
	}
}
int pa[N],pb[N],range[N];
typedef long long LL;
LL cnt[N*2];
void adjust(int x,int c)
{
	for(int i=0;i<n;i++)
	while(pa[x]<range[x]&&!D[x][pa[x]])pa[x]++;
	pb[x]=max(pb[x],pa[x]+1);
	while(pb[x]<range[x]&&!D[x][pb[x]])pb[x]++;
	if(pa[x]>=range[x])return;
	if(D[x][pa[x]]>=2)cnt[pa[x]*2]+=1ll*D[x][pa[x]]*(D[x][pa[x]]-1)/2*c;
	else 
	{
		if(pb[x]>=range[x])return;
		cnt[pa[x]+pb[x]]+=1ll*D[x][pb[x]]*c;
	}
}
void divide(int x)
{
	vis[x]=1;
	extend(x,0,0,x);range[x]=(int)D[x].size();
	pa[x]=0;pb[x]=1;adjust(x,1);
	for(int y:G[x])if(!vis[y])
	{
		int r=0;
		findroot(y,x,siz[y],r);
		fa[r]=x;
		dep[r]=dep[x]+1;
		divide(r);
	}
}
int main()
{
	n=read();
	int C=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		G[x].push_back(y);
		G[y].push_back(x);
	}
	int r=0;
	findroot(1,0,n,r);
	divide(r);
	LL lst=0;
	int now=0;
	exit(0); 
	for(int i=1;i<=n-2;i++)
	{
		LL x;
		scanf("%lld",&x);
		x=(x^(lst*C));
		int u=x;
		while(u)
		{
			adjust(u,-1);
			D[u][dis[x][dep[u]]]--;
			adjust(u,1);
			u=fa[u];
		}
		while(!cnt[now])now++;
		printf("%d %lld\n",now,lst=cnt[now]);
	}
	return 0;
}