标算复杂度似乎是$O(3^{n}*n^2)$的，但可以$O(2^{n}*n^3)$

首先枚举哪些点是叶子。(设枚举的点集为 $s_1$,剩下的点集为 $s_2$)

如何保证一个点 $i$ 是叶子？

只要让 $i$ 往 $s_2$ 连一条边就可以了。

所以方案数 $f[s_1]=$ $s_2$ 的生成树个数 $ \times \prod_{i,i \in s_1}$ $i$ 连向 $s_2$ 的边数。前一项可以用矩阵树求

但这样其实只能保证 ${\textbf s_1}$ 的点是叶子，却不能保证 ${\textbf s_2}$ 的点不是叶子。

现在要求只有 ${\textbf s}$ 的点是叶子的方案数 $ans[s]$，就再容斥一下:

$ ans[s]=\sum_{s',s' \supseteq s } f[s'] * (-1)^{|s'|-|s|} $

这个东西如果暴力的话因为每个点有三种状态所以复杂度$O(3^{n})$

但他其实类似高维前缀和，于是可以$O(2^{n}*n)$

答案就是$\sum_{s,|s|=k} ans[s]$

总复杂度是$\sum_{i=0}^{s} cnt[s-i]^{3}$ , 其中$s=2^{n}-1$,$cnt[s]$ 表示二进制数 $s$ 中 $1$ 的个数

当$n=10$时，这个值为$166400$

但我也不会算，就当它是$O(2^{n}*n^3)$吧

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}

template <typename T> void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}

struct vec
{
    int *a,n;
    void pb(int x)
    {
        if(n==(n&-n))
        {
            int *_a=new int [n*2];
            memcpy(_a,a,n*sizeof(int));
            a=_a;
        }
        a[n++]=x;
    }
};

const int N=10,U=1<<N;
int lk[N][N];
ll f[U];

int q[N];
ll qa[N][N],*a[N];
ll gauss(int m)
{
    ll ans=1;
    for(int i=0;i<m;++i)
    {
        for(int j=i+1;j<m;++j)
        {
            while(a[j][i])
            {
                ll bi=a[i][i]/a[j][i];
                for(int k=i;k<m;++k)
                 a[i][k]-=a[j][k]*bi;

                swap(a[i],a[j]);
                ans=-ans;
            }
        }
        ans*=a[i][i];
    }
    return ans;
}

int main()
{
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);

    for(int i=0;i<N;++i)a[i]=qa[i];

    int n=read(),m=read(),k=read();
    while(m--)
    {
        int x=read()-1,y=read()-1;
        ++lk[x][y];++lk[y][x];
    }
    int u=(1<<n)-1;
    for(int s=1;s<u;++s)
    {
        ll ans=1;

        m=0;
        for(int i=0;i<n;++i)
        if(!(s&(1<<i))) q[m++]=i;
        for(int i=0;i<n;++i)
        if(s&(1<<i)) 
        {
            int cnt=0;
            for(int j=0;j<m;++j) cnt+=lk[i][q[j]];
            ans*=cnt;
        }

        for(int i=0;i<m;++i)
        for(int j=0;j<m;++j)
         a[i][j]=0;

        for(int i=0;i<m;++i)
        for(int j=0;j<i;++j)
        {
          int w=lk[q[i]][q[j]];
          a[i][i]+=w;
          a[j][j]+=w;
          a[i][j]=a[j][i]=-w;
        }

        ans*=gauss(m-1);

        if((n-m-k)%2==1) f[s]=-ans;
        else f[s]=ans;
    }

    for(int i=0;i<n;++i)
    for(int s=0;s<u;++s)
    if( (s&(1<<i))==0 ) f[s]+=f[s+(1<<i)];

    ll ans=0;
    for(int s=0;s<u;++s)
    {
        int cnt=0;
        for(int i=0;i<n;++i)
        if(s&(1<<i))++cnt;
        if(cnt==k)ans+=f[s];
    }
    cout<<ans;
}