#include<string.h>
#include<stdlib.h>
#include<math.h>
int n;
int e[200010],h[100010],nex[200010];
int f[100010][2],del[100010];
void run1(int fa,int x);
void run2(int fa,int x);
int max(int a,int b){return (a>b)?a:b;}
void init(void)
{
int i,x,y,k=0,m;
memset(e,0,sizeof(e));
memset(h,0,sizeof(h));
memset(nex,0,sizeof(nex));
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
for(i=1;i<=n-1;i++)
{
scanf("%d%d",&x,&y);
k++;
e[k]=y;
nex[k]=h[x];
h[x]=k;
k++;
e[k]=x;
nex[k]=h[y];
h[y]=k;
}
if(m==1)
run1(1,1);
else
run2(1,1);
printf("%d",max(f[1][0],f[1][1]));
return;
}
void run2(int fa,int x)
{
int i=h[x];
if(e[i]==fa)
i=nex[i];
if(!i)
{
f[x][0]=0;
f[x][1]=1;
return;
}
f[x][1]=1;
while(i!=0)
{
if(e[i]!=fa)
{
run2(x,e[i]);
f[x][0]+=f[e[i]][0];
del[x]=max(del[x],f[e[i]][1]-f[e[i]][0]);
f[x][1]+=f[e[i]][0]-del[e[i]];
}
i=nex[i];
}
f[x][0]+=del[x];
return;
}
void run1(int fa,int x)
{
int i=h[x];
if(e[i]==fa)
i=nex[i];
if(!i)
{
f[x][0]=0;
f[x][1]=1;
return;
}
f[x][1]=1;
while(i!=0)
{
if(e[i]!=fa)
{
run1(x,e[i]);
f[x][0]+=max(f[e[i]][1],f[e[i]][0]);
f[x][1]+=f[e[i]][0];
}
i=nex[i];
}
return;
}
int main(void)
{
init();
return 0;
}
测试点1 Accepted / 24ms / 5008kB
测试点2 Accepted / 23ms / 5008kB
测试点3 Accepted / 14ms / 5008kB
测试点4 Accepted / 112ms / 7776kB
测试点5 Accepted / 149ms / 5008kB
测试点6 Accepted / 15ms / 5008kB
测试点7 Accepted / 20ms / 5008kB
测试点8 Accepted / 19ms / 5008kB
测试点9 Accepted / 148ms / 8776kB
测试点10 Accepted / 98ms / 5008kB