思路与算法

对每个强制为叶子的点集S计F(S)。n≥3时S中顶点不能互连，删S后余点必须形成一棵生成树；用余点诱导图的拉普拉斯余子式行列式求树数，再乘每个叶子连接余点的度数。若|S|=s，按(-1)^(s-k)C(s,k)加权求和，得到恰k叶子的数量；1、2点单独处理。

正确性说明

任意含S为叶子的树与“余点生成树加各叶子一条接入边”一一对应。矩阵树定理给出余点树数；行列式用Bareiss整数消元，行交换跟踪符号。固定实际叶子数L的树，在总和中的系数为Σs≥k (-1)^(s-k)C(L,s)C(s,k)，L=k时1，否则0，所以恰保留目标树。

复杂度

枚举2^n点集，每次建矩阵及叶度O(n²)、行列式O(n³)，总O(2^n n³)时间，O(n²)临时空间，组合表与邻接初始化O(n²)；n≤10。

易错点

按有标号边集计树。原文旋转示意不表示把不同顶点的同构树合并，三角形样例输出3可核实。余点仅1个时空行列式为1；n=2的两叶相连需要单列。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll det(vector<vector<ll>> a) {
    int n = a.size();
    if (!n)
        return 1;
    ll prev = 1, sgn = 1;
    for (int k = 0; k < n - 1; k++) {
        int p = k;
        while (p < n && !a[p][k])
            p++;
        if (p == n)
            return 0;
        if (p != k) {
            swap(a[p], a[k]);
            sgn = -sgn;
        }
        ll pivot = a[k][k];
        for (int i = k + 1; i < n; i++)
            for (int j = k + 1; j < n; j++)
                a[i][j] = (a[i][j] * pivot - a[i][k] * a[k][j]) / prev;
        for (int i = k + 1; i < n; i++)
            a[i][k] = 0;
        prev = pivot;
    }
    return sgn * a[n - 1][n - 1];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> g(n, vector<int>(n));
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        g[--u][--v] = 1;
        g[v][u] = 1;
    }
    if (n <= 2) {
        cout << (n == 2 && k == 2 ? g[0][1] : n == 1 && k == 0) << '\n';
        return 0;
    }
    ll C[11][11] = {};
    for (int i = 0; i <= 10; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    ll ans = 0;
    for (int S = 0; S < (1 << n); S++) {
        int z = __builtin_popcount((unsigned)S);
        if (z < k || z == n)
            continue;
        vector<int> v;
        for (int i = 0; i < n; i++)
            if (!(S >> i & 1))
                v.push_back(i);
        ll mul = 1;
        for (int i = 0; i < n; i++)
            if (S >> i & 1) {
                int d = 0;
                for (int j : v)
                    d += g[i][j];
                mul *= d;
            }
        int h = v.size();
        vector<vector<ll>> a(h - 1, vector<ll>(h - 1));
        for (int i = 0; i < h - 1; i++) {
            for (int j = 0; j < h; j++)
                if (i != j && g[v[i]][v[j]]) {
                    a[i][i]++;
                    if (j < h - 1)
                        a[i][j]--;
                }
        }
        ll add = det(a) * mul * C[z][k];
        ans += ((z - k) & 1) ? -add : add;
    }
    cout << ans << '\n';
}