hungary

更正：模数1000000007

/*

  最大匹配求p=1的情况能得30分

  正解：树形DP，f[i][0/1]表示i节点向下连的那条边选或不选时的最大值

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#define maxn 100010

#define mod 1000000007

#define ll long long

using namespace std;

ll T,P,n,head[maxn],num,f[maxn][],g[maxn][],L,R[maxn],l,r[maxn],son[maxn];

struct node

{

    ll v,pre;

}e[maxn*];

ll init()

{

    ll x=,f=;char s=getchar();

    while(s<''||s>''){if(s=='')f=-;s=getchar();}

    while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

    return x*f;

}

void Add(ll from,ll to)

{

    num++;e[num].v=to;

    e[num].pre=head[from];

    head[from]=num;

}

void Clear()

{

    num=;

    memset(f,,sizeof(f));

    memset(g,,sizeof(g));

    memset(head,,sizeof(head));

}

void DP(ll now,ll from)

{

    g[now][]=;

    ll mx,sum;

    for(int i=head[now];i;i=e[i].pre)

    {

        ll v=e[i].v;

        if(v==from)continue;

        DP(v,now);//x不连儿子 儿子们可连可不连

        mx=max(f[v][],f[v][]);sum=;

        if(mx==f[v][])sum+=g[v][];

        if(mx==f[v][])sum+=g[v][];

        g[now][]=g[now][]*sum%mod;

        f[now][]+=mx;

    }

    //x连某个儿子 这个不选 其他的连或者不连

    L=;l=;ll S=;

    for(int i=head[now];i;i=e[i].pre)

        if(e[i].v!=from)son[++S]=e[i].v;

    R[S+]=;r[S+]=;

    for(int i=S;i>=;i--)//预处理一个后缀和，R[i]表示i的后缀匹配数,r[i]为方案数

    {

        ll v=son[i];sum=;

        mx=max(f[v][],f[v][]);

        if(mx==f[v][])sum+=g[v][];

        if(mx==f[v][])sum+=g[v][];

        R[i]=R[i+]+mx;

        r[i]=r[i+]*sum%mod;

    }

    for(int i=;i<=S;i++)//L是前缀和，不断累加

    {

        ll v=son[i];//枚举now连的是哪个儿子

        mx=L+f[v][]+R[i+]+;

        if(mx>f[now][])

        {

            f[now][]=mx;

            g[now][]=l*g[v][]%mod*r[i+]%mod;

        }

        else if(mx==f[now][])

            g[now][]=(g[now][]+l*g[v][]%mod*r[i+]%mod)%mod;

        sum=;

        mx=max(f[v][],f[v][]);

        if(mx==f[v][])sum+=g[v][];

        if(mx==f[v][])sum+=g[v][];

        l=l*sum%mod;L+=mx;

    }

}

int main()

{

    freopen("hungary.in","r",stdin);

    freopen("hungary.out","w",stdout);

    T=init();P=init();

    while(T--)

    {

        n=init();

        ll u,v;Clear();

        for(int i=;i<n;i++)

        {

            u=init();v=init();

            Add(u,v);Add(v,u);

        }

        DP(,);ll sum,mx;

        mx=max(f[][],f[][]);sum=;

        if(mx==f[][])sum+=g[][],sum%=mod;

        if(mx==f[][])sum+=g[][],sum%=mod;

        if(P==)cout<<mx<<endl;

        if(P==)cout<<mx<<" "<<sum<<endl;

    }

    return ;

}