#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 3010;
const LL P = 1e9 + 7;
 
LL qpow(LL a, LL b) {
    LL c = 1;
    while(b) {
        if (b & 1) c = c * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return c;
}
 
int n;
vector<int> G[N]; 
int siz[N];            // 子树大小
 
// f[u][i]：在 u 的子树内，不选 u，选 i 个次级城市的方案数
// F[u][i]：在 u 的子树内，允许选 u 作为次级城市时，选 i 个次级城市的方案数
// g[u][i]：在整棵树中，除去 u 的子树（即父方向），选 i 个次级城市的方案数
LL f[N][N], F[N][N], g[N][N];
 
LL f1[N], f2[N], ans[N];
 
// 第一次 DFS：自底向上计算 f 和 F
void dfsa(int u, int fa) {
    siz[u] = 0;
    f[u][0] = 1; // 不选任何城市，方案数为1
 
    // 遍历所有儿子
    for(int v : G[u]) if(v != fa) {
        dfsa(v, u); // 先递归处理儿子
 
        // 将当前已经合并的子树 f[u] 与 儿子 v 的 F[v] 进行卷积（多项式乘法）
        // 枚举当前已合并大小 i，和儿子子树大小 j
        for (int i = 0; i <= siz[u]; i ++) {
            for (int j = 0; j <= siz[v]; j ++) {
                f1[i + j] = (f1[i+j] + f[u][i] * F[v][j] % P) % P;
                // 当前取 i 个，儿子取 j 个，总共 i+j 个
            }
        }
        // 合并大小累加
        siz[u] += siz[v];
        // 将临时数组拷贝回 f[u]
        for (int i = 0; i <= siz[u]; i ++) {
            f[u][i] = f1[i];
            f1[i] = 0; // 清空临时数组，准备下次合并
        }
    }
 
    // 子树大小加上 u 自身
    siz[u] ++;
 
    // F[u] 初始等于 f[u]（代表不选 u 的情况）
    for (int i = 0; i <= siz[u]; i ++) {
        F[u][i] = f[u][i];
    }
    // 但 F[u] 允许选 u 作为次级城市：
    // 如果选了 u，则子树内其他城市都不能选，所以规模为 1 的方案数 +1
    F[u][1] = (F[u][1] + 1) % P;
}
 
// 第二次 DFS：自顶向下换根，计算 g（父方向的多项式）
void dfsb(int u, int fa) {
    // 先计算以 u 为根时，所有方向（子树内 + 父方向）合并的结果 f2
    // 即 f2 = f[u] * g[u] （多项式乘法）
    memset(f2, 0, sizeof(f2)); // 清空临时数组
    for (int i = 0; i <= siz[u]; i ++) {
        for (int j = 0; j <= n - siz[u]; j ++) {    // 父方向最多 n - siz[u] 个点
            f2[i + j] = (f2[i + j] + f[u][i] * g[u][j]) % P;
        }
    }
 
    // 遍历每个儿子 v，利用 f2 反推 g[v]
    for(int v : G[u]) if(v != fa) {
        // 把 f2 拷贝到 f1 中，我们将在 f1 上做"除法"来去掉 F[v] 的贡献
        memcpy(f1, f2, sizeof(f2));
 
        // 找到 F[v] 的最高非零次项（为了做长除法）
        int mx = siz[v];
        while (mx >= 0 && F[v][mx] == 0) mx--;
 
        // 求 F[v] 最高次项系数的逆元，用于除法
        LL inv = qpow(F[v][mx], P - 2);
 
        // 从高次项向低次项进行多项式长除法：
        // 已知 f1 = (其他部分) * F[v]，要求出"其他部分"存在 tmp 里，即 g[v]
        for(int i = n; i >= mx; i--) {
            if(f1[i] == 0) continue;
 
            // cnt 就是商在这一项的系数
            LL cnt = f1[i] * inv % P;
            // 存到 g[v] 中，注意 g[v] 的次数要减去 F[v] 的最高次 mx
            g[v][i - mx] = cnt;
 
            // 用这个系数去消去 f1 中由 F[v] 产生的所有贡献（减去 F[v] * cnt）
            for (int j = mx, k = i; j >= 0; j --, k --) {
                f1[k] = (f1[k] - (F[v][j] * cnt % P) + P) % P;
            }
        }
 
        // 得到除去 v 子树的"兄弟+父方向"多项式后，
        // 还要考虑将 u 自己作为次级城市的情况（如果选了 u，其他方向都不能选）
        // 因此 g[v][1] 方案数 +1
        g[v][1] = (g[v][1] + 1) % P;
    }
 
    // 递归处理儿子们
    for(int v : G[u]) if(v != fa) {
        dfsb(v, u);
    }
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	 
    cin >> n;
    for (int i = 1; i < n; i ++) {
    	int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
	
	memset(f, 0, sizeof(f));
	memset(F, 0, sizeof(F));
	memset(g, 0, sizeof(g));
    // 以 1 为根，进行第一次自底向上 DP
    dfsa(1, 0);
 
    // 根节点 1 没有父方向，所以 g[1][0] = 1（空集一种方案）
    g[1][0] = 1;
    // 进行第二次换根 DP，计算所有点的 g
    dfsb(1, 0);
 
    // 最后统计答案：
    // 枚举每个点作为首都 u
    // 从子树内选 x 个（f[u][x]），从父方向选 y 个（g[u][y]）
    // 总规模 = x + y + 1（加上首都自己）
    for (int u = 1; u <= n; u ++) {
        for (int x = 0; x <= siz[u]; x ++) {
            for (int y = 0; y <= n - siz[u]; y ++) {
                ans[x + y + 1] = (ans[x + y + 1] + f[u][x] * g[u][y]) % P;
            }
        }
    }
 
    for (int i = 1; i <= n; i ++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
    return 0;
}

怎么大家都会不依赖深度的做法 /ll 来一个依赖深度的退背包做法。

看完这个题，我会 $O(n^3)$！枚举根节点，然后记 $f_{i,j}$ 为 $i$ 节点的子树内选了 $j$ 个关键节点的方案数，每次只需要让 $f_{u,1} \leftarrow f_{u,1} + 1$ 就可以了。

考虑换根。用 $F_{i,j}$ 继承上面的定义，让 $f_{i,j}$ 为不考虑 $i$ 节点本身被选中的情况数（其实就是 $F_{i,1} = f_{i,1} + 1$），设 $g_{i,j}$ 为 $i$ 节点子树外选 $j$ 个节点的方案数，从上往下转移就是你要合并前后缀的 $f$ 与 $g_{fa}$。

发现这个东西和 recollector 很像，但是还要包含 $g_{fa}$。我们考虑类似的处理手法，具体就是退背包解决。

设现在从 $u$ 转移到 $v$，每次先让 $f_{u}$ 和 $g_{u}$ 合并，记为 $h_{u}$，然后每次要从 $h_{u}$ 中去掉 $F_{v}$ 的贡献得到 $g_{v}$。

分析一下复杂度，合并 $f_u$ 和 $g_u$ 的复杂度是 $O(\sum siz(n-siz))$，$h_u$ 的大小是 $n$，从 $h_u$ 中去掉 $F_v$ 的贡献复杂度也是 $O(\sum siz(n-siz))$。

发现这个复杂度相当于枚举每一条边，左右两边子树大小乘起来。对于一个点对 $(u,v)$，它会产生的贡献为两点路径的边数，最大是题目中的常数 $36$，因此这个算法的复杂度是 $O(n^2 l)$，其中 $l$ 为两点间距离，也可以理解为深度。

::::info[Code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3010,mod = 1e9+7;

ll qpow(ll a,int b)
{
    ll ret=1;
    while(b)
    {
        if(b&1) ret = ret*a % mod;
        a = a*a % mod;
        b >>= 1;
    }
    return ret;
}

int n;
vector<int> e[N];
int siz[N];
ll f[N][N],F[N][N],g[N][N];
ll f1[N],f2[N],ans[N];

void dfs(int u,int fa)
{
    siz[u] = 0;
    f[u][0] = 1;
    for(int v:e[u])
    {
        if(v == fa) continue;
        dfs(v,u);
        for(int i=0;i<=siz[u];i++)
        {
            for(int j=0;j<=siz[v];j++)
            {
                f1[i+j] = (f1[i+j] + f[u][i] * F[v][j] % mod) % mod;
            }
        }
        siz[u] += siz[v];
        for(int i=0;i<=siz[u];i++)
        {
            f[u][i] = f1[i];
            f1[i] = 0;
        }
    }
    siz[u]++;
    // cerr << " ---- " << u << " ----\n";
    for(int i=0;i<=siz[u];i++)
    {
        F[u][i] = f[u][i];
        // cerr << f[u][i] << ' ';
    }
    // cerr << '\n';
    F[u][1] = (F[u][1] + 1) % mod;
    // for(int i=0;i<=siz[u];i++)
    // {
    //     cerr << F[u][i] << ' ';
    // }
    // cerr << '\n';
}

void dfs1(int u,int fa)
{
    int tot=0;
    memset(f2,0,sizeof(f2));
    for(int i=0;i<=siz[u];i++)
    {
        for(int j=0;j<=n-siz[u];j++)
        {
            f2[i+j] = (f2[i+j] + f[u][i] * g[u][j]) % mod;
        }
    }
    for(int v:e[u]) // f[u] = g[v] * F[v]
    {
        if(v == fa) continue;
        memcpy(f1,f2,sizeof(ll)*(n+1));
        int mx=siz[v];
        while(!F[v][mx]) mx--;
        ll inv = qpow(F[v][mx],mod-2);
        for(int i=n;i>=mx;i--)
        {
            if(f1[i])
            {
                ll cnt = f1[i] * inv % mod;
                g[v][i-mx] = cnt;
                for(int j=mx,k=i;j>=0;j--,k--)
                {
                    f1[k] = (f1[k] - (F[v][j] * cnt % mod) + mod) % mod;
                }
            }
        }
        g[v][1] = (g[v][1] + 1) % mod;
    }
    for(int v:e[u])
    {
        if(v == fa) continue;
        dfs1(v,u);
    }
}

int main()
{
    cin >> n;
    for(int i=1,u,v;i<n;i++)
    {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    g[1][0] = 1;
    dfs1(1,0);
    for(int u=1;u<=n;u++)
    {
        for(int x=0;x<=siz[u];x++)
        {
            for(int y=0;y<=n-siz[u];y++)
            {
                ans[x+y+1] = (ans[x+y+1] + f[u][x] * g[u][y]) % mod;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout << ans[i] << ' ';
    }
}

:::: 跑的没有 $O(n^2)$ 快，你们有点厉害了qaq