#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define next nxt
int point[100003],next[200003],v[200003],cnt=0,N,l[100003],r[100003],pre[100003],con[100003];
const long long mo=1000000007;
long long f[100003][2][2];
int dp[100003][2][2];
bool p[100003];
void memsetf(){for(int i=0;i<=N;++i)for(int j=0;j<2;++j)for (int k=0;k<2;++k)f[i][j][k]=1;}
void insect(int x,int y){next[cnt]=point[x];point[x]=cnt;v[cnt]=y;cnt++;}
void dfs(int x)
{
    if (x==0) return;
    int i,j=0;
    for (i=point[x];i!=-1;i=next[i])
     if (p[v[i]]==0)
     {
         p[v[i]]=1;
         if (l[x]==0) {l[x]=v[i];j=v[i];}
         else {r[j]=v[i];pre[v[i]]=j;j=v[i];}
     }
    dfs(j); con[j]=con[l[j]]+1;
    while (pre[j]!=-1){j=pre[j]; dfs(j); con[j]=con[l[j]]+con[r[j]]+1;}
}
void work(int x)
{
    if (r[x]!=0) work(r[x]);
    if (l[x]!=0) work(l[x]);
    long long s=0; int num=1000000008;
    if ((l[x]==0)&&(r[x]==0))
    {
        dp[x][0][1]=1; dp[x][0][0]=1; dp[x][1][0]=0; return;
    }
    else
    if (l[x]==0)
    {
        dp[x][0][1]=1+dp[r[x]][0][0]; f[x][0][1]=f[r[x]][0][0];
        dp[x][0][0]=1+dp[r[x]][0][0]; f[x][0][0]=f[r[x]][0][0];
        dp[x][1][0]=dp[r[x]][1][0]; f[x][1][0]=f[r[x]][1][0];
        return;
    }
    else
    if (r[x]==0)
    {
        dp[x][0][1]=1+dp[l[x]][1][0]; f[x][0][1]=f[l[x]][1][0];
        //dp[x][0][0]=min(1+dp[l[x]][1][0],dp[l[x]][0][1]);
        if (1+dp[l[x]][1][0]<dp[l[x]][0][1])
         dp[x][0][0]=1+dp[l[x]][1][0],f[x][0][0]=f[l[x]][1][0];
        else
         if (1+dp[l[x]][1][0]>dp[l[x]][0][1])
          dp[x][0][0]=dp[l[x]][0][1],f[x][0][0]=f[l[x]][0][1];
         else
          dp[x][0][0]=dp[l[x]][0][1],f[x][0][0]=(f[l[x]][1][0]+f[l[x]][0][1])%mo;
        //dp[x][1][0]=min(1+dp[l[x]][1][0],dp[l[x]][0][0]);
        if (1+dp[l[x]][1][0]<dp[l[x]][0][0])
         dp[x][1][0]=1+dp[l[x]][1][0],f[x][1][0]=f[l[x]][1][0];
        else
         if (1+dp[l[x]][1][0]>dp[l[x]][0][0])
          dp[x][1][0]=dp[l[x]][0][0],f[x][1][0]=f[l[x]][0][0];
         else
          dp[x][1][0]=dp[l[x]][0][0],f[x][1][0]=(f[l[x]][1][0]+f[l[x]][0][0])%mo;
        return;
    }
    //dp[x][0][1]=min(dp[x][0][1],dp[l[x]][0][1]+dp[r[x]][0][1]);
    //dp[x][0][1]=min(dp[x][0][1],1+dp[l[x]][1][0]+dp[r[x]][0][0]);
    if (dp[l[x]][0][1]+dp[r[x]][0][1]<1+dp[l[x]][1][0]+dp[r[x]][0][0])
     dp[x][0][1]=dp[l[x]][0][1]+dp[r[x]][0][1],f[x][0][1]=(f[l[x]][0][1]*f[r[x]][0][1])%mo;
    else
     if (dp[l[x]][0][1]+dp[r[x]][0][1]>1+dp[l[x]][1][0]+dp[r[x]][0][0])
      dp[x][0][1]=1+dp[l[x]][1][0]+dp[r[x]][0][0],f[x][0][1]=(f[l[x]][1][0]*f[r[x]][0][0])%mo;
     else
      {
          dp[x][0][1]=1+dp[l[x]][1][0]+dp[r[x]][0][0];
        f[x][0][1]=((f[l[x]][0][1]*f[r[x]][0][1])%mo+(f[l[x]][1][0]*f[r[x]][0][0])%mo)%mo;
      }
    //dp[x][0][0]=min(dp[x][0][0],dp[l[x]][0][1]+dp[r[x]][0][0]);
    //dp[x][0][0]=min(dp[x][0][0],1+dp[l[x]][1][0]+dp[r[x]][0][0]);
    if (dp[l[x]][0][1]+dp[r[x]][0][0]<1+dp[l[x]][1][0]+dp[r[x]][0][0])
     dp[x][0][0]=dp[l[x]][0][1]+dp[r[x]][0][0],f[x][0][0]=(f[l[x]][0][1]*f[r[x]][0][0])%mo;
    else
     if (dp[l[x]][0][1]+dp[r[x]][0][0]>1+dp[l[x]][1][0]+dp[r[x]][0][0])
      dp[x][0][0]=1+dp[l[x]][1][0]+dp[r[x]][0][0],f[x][0][0]=(f[l[x]][1][0]*f[r[x]][0][0])%mo;
     else
      {
          dp[x][0][0]=1+dp[l[x]][1][0]+dp[r[x]][0][0];
          f[x][0][0]=((f[l[x]][1][0]*f[r[x]][0][0])%mo+(f[l[x]][0][1]*f[r[x]][0][0])%mo)%mo;
      }
    //dp[x][1][0]=min(dp[x][1][0],dp[l[x]][0][0]+dp[r[x]][1][0]);
    //dp[x][1][0]=min(dp[x][1][0],1+dp[l[x]][1][0]+dp[r[x]][1][0]);
    if (dp[l[x]][0][0]+dp[r[x]][1][0]<1+dp[l[x]][1][0]+dp[r[x]][1][0])
     dp[x][1][0]=dp[l[x]][0][0]+dp[r[x]][1][0],f[x][1][0]=(f[l[x]][0][0]*(f[r[x]][1][0]))%mo;
    else
     if (dp[l[x]][0][0]+dp[r[x]][1][0]>1+dp[l[x]][1][0]+dp[r[x]][1][0])
      dp[x][1][0]=1+dp[l[x]][1][0]+dp[r[x]][1][0],f[x][1][0]=(f[l[x]][1][0]*f[r[x]][1][0])%mo;
     else
      {
          dp[x][1][0]=1+dp[l[x]][1][0]+dp[r[x]][1][0];
          f[x][1][0]=((f[l[x]][0][0]*(f[r[x]][1][0]))%mo+(f[l[x]][1][0]*f[r[x]][1][0])%mo)%mo;
      }
}
int main()
{
    memset(point,-1,sizeof(point));
    memset(next,-1,sizeof(next));
    memset(pre,-1,sizeof(pre));
    memset(dp,50,sizeof(dp));
    memset(v,0,sizeof(v));
    memset(p,0,sizeof(p));
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    scanf("%d\n",&N);
    memsetf();
    int i,x,y;
    for (i=1;i<N;++i)
    {
        scanf("%d %d\n",&x,&y);
        insect(x,y);insect(y,x);
    }p[1]=1;dfs(1);
    work(l[1]);
    if (dp[l[1]][0][1]<(1+dp[l[1]][1][0]))
     printf("%d\n%lld\n",dp[l[1]][0][1],f[l[1]][0][1]);
    else
     if (dp[l[1]][0][1]>(1+dp[l[1]][1][0]))
      printf("%d\n%lld\n",1+dp[l[1]][1][0],f[l[1]][1][0]);
     else
      printf("%d\n%lld\n",1+dp[l[1]][1][0],(f[l[1]][0][1]+f[l[1]][1][0])%mo);
    return 0;
}

题解在这里

虽然我没有AC但我来抢个沙发