满分解法（100 分）

先看同一深度内能怎样移动

以顶点 $1$ 为根，记顶点 $u$ 的深度为 $\operatorname{dep}(u)$，深度为 $d$ 的顶点集合为 $L_d$，其大小为 $c_d$，最大深度为 $H$。深度非递减意味着排列一定先写完 $L_0$，再写完 $L_1$，依次直到 $L_H$。需要决定的只有各层内部的顺序，以及相邻两层之间怎样衔接。

固定询问 $K$，令 $r=\lfloor K/2\rfloor$。同层顶点 $u,v\in L_d$ 满足

$$d(u,v)=2\bigl(d-\operatorname{dep}(\operatorname{lca}(u,v))\bigr).$$

因此，当 $d>r$ 时，$d(u,v)\le K$ 等价于它们在深度 $d-r$ 处的祖先相同；当 $d\le r$ 时，该层任意两点的距离都不超过 $K$。

这给出了同层顶点的一个划分：同一类内任意两点都能相邻，不同类之间任何两点都不能相邻。一层在排列中必须连续出现，所以若一层含有两个非空类，无论怎样排列，都必然在某处跨类，因而无解。反过来，只有一个类时，这一层内部可以任意排列。

注意这里能从“相邻点距离受限”推出“同层所有点对距离受限”，依靠的是上述祖先等价类结构；对一般图不能这样推断。

用一个数概括所有层内限制

定义

$$R=\max_{d}\max_{u,v\in L_d}\frac{d(u,v)}2.$$

同层距离均为偶数，$R$ 是整数。上一节说明：只要 $K<2R$，就有一层无法排完，答案为 $0$；只要 $K\ge 2R$，每一层内部都可以任意排列。

不必枚举同层点对。记 $h(u)$ 为从 $u$ 向下到后代的最大距离。对 $u$ 的每个孩子 $v$，分支高度为 $h(v)+1$；令 $b(u)$ 为这些高度中的第二大值，不足两条分支时补 $0$。于是

$$h(u)=\max\left(\{0\}\cup\{h(v)+1:v\text{ 是 }u\text{ 的孩子}\}\right), \qquad R=\max_u b(u).$$

证明分两面。两条最高分支都能走到距 $u$ 恰为 $b(u)$ 的位置，这两个点同深度、最近公共祖先为 $u$，距离为 $2b(u)$。另一方面，任意不同的同层点 $x,y$，设最近公共祖先为 $u$，它们位于 $u$ 的两条不同分支，并且离 $u$ 一样远。这段距离不超过两条分支高度的较小者，也就不超过 $b(u)$。两边合起来便得到公式。

一次后序遍历维护每个点的最高、次高分支即可得到 $R$，同时统计父亲、深度和各层大小。

大于临界值时，层间也完全自由

考虑相邻两层的任意顶点 $u\in L_d$、$v\in L_{d+1}$，令 $w$ 为 $v$ 的父亲。$u,w$ 同层，所以

$$d(u,v)\le d(u,w)+1\le 2R+1.$$

因此，只要 $K\ge 2R+1$，层内和层间都没有额外限制，各层独立排列，答案为

$$A=\prod_{d=0}^{H}c_d!\pmod{10^9+7}.$$

所有询问中，只剩下偶数临界值 $K=2R$ 需要单独计算。若 $R=0$，每层只能有一个顶点，树从根看是一条链；所有合法询问都有 $K\ge1$，答案恒为 $1$，无需计算临界情形。

临界值只限制上一层的最后一个点

下面设 $R\ge1$，固定某个 $0\le d<H$。下一层 $L_{d+1}$ 的点对距离都不超过 $2R$，所以它们在深度

$$t_d=\max(0,d+1-R)$$

处有同一个祖先，记为 $z_d$。

若 $t_d=0$，则对任何 $u\in L_d,v\in L_{d+1}$，都有 $d(u,v)\le2d+1\le2R-1$，这两层可以任意衔接。

若 $t_d>0$，则存在一个恰好描述衔接是否合法的条件：上一层的末尾顶点 $u$ 必须位于 $z_d$ 的子树内。

当 $u$ 在该子树内时，任取下一层顶点 $v$，两者最近公共祖先的深度至少为 $t_d$，因此

$$d(u,v)\le 2d+1-2t_d=2R-1.$$

当 $u$ 不在该子树内时，最近公共祖先严格高于 $z_d$，深度至多为 $t_d-1$，从而

$$d(u,v)\ge 2d+1-2(t_d-1)=2R+1.$$

所以一个末尾顶点要么能接下一层的所有顶点，要么一个都接不上。衔接没有限制下一层的第一个点，因而不同层的内部排列仍能独立计数。

令

$$a_d=|L_d\cap\operatorname{subtree}(z_d)|.$$

第 $d$ 层的末尾有 $a_d$ 种选择，剩下的 $c_d-1$ 个顶点任意排列；最深层没有后继层，可以完全自由。临界答案为

$$B=c_H!\prod_{d=0}^{H-1}\left(a_d(c_d-1)!\right)\pmod{10^9+7}.$$

例如第二组原样例的三层为 $\{1\}$、$\{2,3\}$、$\{4,5,6\}$。有 $R=1$，临界询问为 $K=2$。深度 $1$ 的末尾必须是顶点 $3$，因为只有它能以距离 $1$ 接到下一层；顶点 $2$ 到下一层的距离都是 $3$。该层只能排成 $[2,3]$，最深层有 $3!$ 种顺序，因此临界答案是 $6$。当 $K\ge3$ 时，深度 $1$ 的两种顺序都可用，答案变为 $2!\cdot3!=12$。

一次遍历求出全部层尾数量

还需高效求出所有 $a_d$。任取一个最深顶点，把它的根路径记为

$$w_0=1,w_1,\ldots,w_H,\qquad\operatorname{dep}(w_t)=t.$$

由于 $w_{d+1}$ 本身属于 $L_{d+1}$，该层共同祖先必然就是 $z_d=w_{t_d}$。这样，所有待查询的子树根都在这条路径上，不需要分别计算每层的最近公共祖先。

当 $d<R$ 时，$z_d$ 是根，直接令 $a_d=c_d$。其余层可写成：对每个 $1\le t\le H-R$，求

$$a_{t+R-1}=|\operatorname{subtree}(w_t)\cap L_{t+R-1}|.$$

每个这样的路径顶点只附带一个目标深度。再做一次深度优先遍历，用 $s_j$ 记录到当前时刻为止，累计已经进入过的深度为 $j$ 的顶点数。计数只增不减，退出子树时不撤销。

对于带查询的顶点 $w_t$，设目标深度为 $j=t+R-1$。进入该顶点之前记下 $s_j$；遍历完整棵子树之后，用此时的 $s_j$ 减去进入前的值。深度优先遍历在这两个时刻之间恰好访问了该子树的全部顶点，差值就是所求的 $a_j$。每个点进入一次，每个查询做一次差分，总计线性时间。

最终对每个询问输出

$$f(K)= \begin{cases} 0,&K<2R,\\ B,&K=2R,\\ A,&K>2R. \end{cases}$$

代码中的 radius 对应 $R$，all 对应 $A$，critical 对应 $B$，good[d] 对应 $a_d$。阶乘预处理包含 $0!=1$，所以单点层和单点树均自然成立。

复杂度

时间复杂度为 $O(N+Q)$。两次树遍历、阶乘预处理和逐层求积均为线性时间，每个询问只需常数次比较。

空间复杂度为 $O(N)$。邻接表、每个顶点的状态、各层计数与递归栈均为线性大小。多组测试的总时间为 $O(\sum N+\sum Q)$，峰值空间由单组最大的 $N$ 决定。

AC 代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
  constexpr int mod = 1000000007;
  int n, q;
  cin >> n >> q;
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> parent(n, -1), depth(n), height(n), cnt(n);
  int radius = 0, deepest = 0;
  auto dfs = [&](auto&& self, int u, int p) -> void {
    parent[u] = p;
    cnt[depth[u]]++;
    if (depth[u] > depth[deepest]) deepest = u;
    int first = 0, second = 0;
    for (int v : g[u]) {
      if (v == p) continue;
      depth[v] = depth[u] + 1;
      self(self, v, u);
      int cur = height[v] + 1;
      if (cur > first) {
        second = first;
        first = cur;
      } else {
        second = max(second, cur);
      }
    }
    height[u] = first;
    radius = max(radius, second);
  };
  dfs(dfs, 0, -1);
  int h = depth[deepest];
  vector<int> fact(n + 1, 1);
  for (int i = 1; i <= n; i++) fact[i] = 1LL * fact[i - 1] * i % mod;
  i64 all = 1;
  for (int d = 0; d <= h; d++) all = all * fact[cnt[d]] % mod;

  i64 critical = all;
  if (radius > 0) {
    vector<int> path;
    for (int u = deepest; u != -1; u = parent[u]) path.push_back(u);
    reverse(path.begin(), path.end());
    vector<int> target(n, -1), seen(n), good = cnt;
    for (int t = 1; t <= h - radius; t++) target[path[t]] = t + radius - 1;
    auto count = [&](auto&& self, int u, int p) -> void {
      int d = target[u];
      int before = d == -1 ? 0 : seen[d];
      seen[depth[u]]++;
      for (int v : g[u]) {
        if (v != p) self(self, v, u);
      }
      if (d != -1) good[d] = seen[d] - before;
    };
    count(count, 0, -1);
    critical = fact[cnt[h]];
    for (int d = 0; d < h; d++) {
      critical = critical * good[d] % mod * fact[cnt[d] - 1] % mod;
    }
  }
  for (int i = 0; i < q; i++) {
    int k;
    cin >> k;
    i64 ans = k < 2 * radius ? 0 : k == 2 * radius ? critical : all;
    cout << ans << ' ';
  }
  cout << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int T;
  cin >> T;
  while (T--) solve();
}

全点对距离与逐层端点动态规划（通过子任务 1、3，共 28 分）

先让层内顺序完全自由

本方法使用子任务 $3$ 的 $\sum N\le3000$、$Q\le5$，也能覆盖子任务 $1$。先从每个顶点出发遍历整棵树，保存所有点对距离。以顶点 $1$ 为根，把同深度顶点放在同一层 $L_d$ 中。

对一次询问 $K$，令 $r=\lfloor K/2\rfloor$。深度为 $d$ 的两点距离不超过 $K$，当且仅当它们在深度 $\max(0,d-r)$ 处的祖先相同。因此同层顶点会被划分为若干个类，类内完全可达，类间完全不可达。排列必须连续写完整层，故只要一层存在距离超过 $K$ 的点对，就无解；否则每层内部任意相邻都合法。

利用已经求出的距离表，枚举同层点对检查这一条件。全部满足后，只需处理层与层之间的衔接。

状态记录上一层的末尾

固定 $K$。对 $v\in L_d$，定义 $f(v)$ 为已经排列完 $L_0,L_1,\ldots,L_d$，且最后一个顶点恰为 $v$ 的合法排列数量。初始条件为

$$f(1)=1.$$

对于当前层 $L_d$ 的顶点 $v$，定义辅助量 $g(v)$：前面各层已经合法排完，并且下一步把 $v$ 作为当前层第一个顶点时，已有的排列数量。于是

$$g(v)=\sum_{\substack{u\in L_{d-1}\\d(u,v)\le K}}f(u).$$

如果当前层只有一个顶点 $v$，它既是开头也是结尾，直接有 $f(v)=g(v)$。

如果当前层有 $s\ge2$ 个顶点，固定末尾为 $x$。首点可以取任何 $v\ne x$；固定首尾后，中间 $s-2$ 个点任意排列，贡献 $(s-2)!$。因此

$$f(x)=(s-2)!\sum_{\substack{v\in L_d\\v\ne x}}g(v) =(s-2)!\left(\sum_{v\in L_d}g(v)-g(x)\right).$$

计算时先得到这一层所有 $g(v)$ 及其总和，再同时求各个末尾状态，避免重复对每个末尾枚举所有首点。所有加减乘法均对 $10^9+7$ 取模，减法需归一化为非负数。

例如某层有三个点 $a,b,c$，从上一层转入它们的已有方案数分别为 $2,3,5$。若该层以 $a$ 结尾，首点只能是 $b$ 或 $c$，各自剩下的中间点唯一，因此有 $3+5=8$ 种。以 $b,c$ 结尾时分别为 $7,5$ 种。这正是先求总和 $10$，再减去对应 $g$ 值的过程。

按深度递增计算，到最深层 $L_H$ 后，答案为

$$\sum_{v\in L_H}f(v).$$

每次转移唯一确定上一层末尾、当前层首尾及内部顺序，枚举的情况互不重叠；距离条件保证衔接合法，层内检查保证内部顺序合法，因此递推既充分又完整。

复杂度

时间复杂度为 $O(N^2(Q+1))$。点对距离预处理为 $O(N^2)$，每次询问的同层检查与相邻层转移总共至多枚举 $O(N^2)$ 对顶点。

空间复杂度为 $O(N^2)$，包括距离表和线性的每顶点状态。平方距离表决定了这一方法不适合完整范围中的大树。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
  constexpr int mod = 1000000007;
  int n, q;
  cin >> n >> q;
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<vector<int>> dist(n, vector<int>(n));
  for (int s = 0; s < n; s++) {
    auto dfs = [&](auto&& self, int u, int p) -> void {
      for (int v : g[u]) {
        if (v == p) continue;
        dist[s][v] = dist[s][u] + 1;
        self(self, v, u);
      }
    };
    dfs(dfs, s, -1);
  }
  int h = *max_element(dist[0].begin(), dist[0].end());
  vector<vector<int>> layer(h + 1);
  for (int u = 0; u < n; u++) layer[dist[0][u]].push_back(u);
  vector<int> fact(n + 1, 1);
  for (int i = 1; i <= n; i++) fact[i] = 1LL * fact[i - 1] * i % mod;
  auto query = [&](int k) -> int {
    for (const auto& row : layer) {
      for (int u : row) {
        for (int v : row) {
          if (dist[u][v] > k) return 0;
        }
      }
    }
    vector<int> dp(n), incoming(n);
    dp[0] = 1;
    for (int d = 1; d <= h; d++) {
      int sum = 0;
      for (int v : layer[d]) {
        for (int u : layer[d - 1]) {
          if (dist[u][v] <= k) incoming[v] = (incoming[v] + dp[u]) % mod;
        }
        sum = (sum + incoming[v]) % mod;
      }
      int len = layer[d].size();
      for (int v : layer[d]) {
        dp[v] = len == 1 ? incoming[v] : 1LL * ((sum - incoming[v] + mod) % mod) * fact[len - 2] % mod;
      }
    }
    int ans = 0;
    for (int v : layer[h]) ans = (ans + dp[v]) % mod;
    return ans;
  };
  for (int i = 0; i < q; i++) {
    int k;
    cin >> k;
    cout << query(k) << ' ';
  }
  cout << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int T;
  cin >> T;
  while (T--) solve();
}

距离不超过二的同父层计数（通过子任务 2，共 12 分）

只考虑距离上限为一或二

本方法使用子任务 $2$ 的 $K_i\le\min(2,N)$。以顶点 $1$ 为根，记深度为 $d$ 的顶点数为 $c_d$，最大深度为 $H$。深度非递减要求每一层连续出现。

当 $K=1$ 时，两个不同的同层顶点之间距离至少为 $2$，不能相邻。因此有解当且仅当每层只有一个顶点，也就是从根开始只有一条链。此时按深度排列唯一，答案为 $1$；否则答案为 $0$。

距离上限为二时的同父条件

同层两个不同顶点距离不超过 $2$，当且仅当它们拥有同一个父亲。一层若包含不同父亲的孩子，就会被分为若干个类，类间任何两点都不能相邻，无法连续排完这一层。因此，首先检查每个非根层是否所有顶点同父；有一层不满足，便有 $f(2)=0$。

如果条件成立，设深度 $d+1$ 的所有顶点的共同父亲为 $x$。上一层末尾为 $x$ 时，到下一层任意点距离为 $1$；末尾若是其他顶点 $y$，由于 $x,y$ 同层且不同，到下一层的距离至少为 $3$。所以第 $d$ 层必须以 $x$ 结尾。

除了末尾固定，其余 $c_d-1$ 个点都是同父顶点，可以任意排列。最深层没有下一层，可以完全自由。于是

$$f(2)=c_H!\prod_{d=0}^{H-1}(c_d-1)!\pmod{10^9+7}.$$

一次树遍历统计每层大小、记录每层第一次遇到的父亲并比较后续父亲；再预处理阶乘即可计算两个答案。对于 $N=1$，只有 $K=1$，唯一排列自然合法。

复杂度与适用范围

时间复杂度为 $O(N+Q)$，空间复杂度为 $O(N)$。

提交代码按本子任务只区分 $K=1$ 与 $K=2$。它不计算更大距离上限的答案；例如原样例第二棵树在 $K=3$ 时多出的排列，就不能用这里的同父条件计数。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
  constexpr int mod = 1000000007;
  int n, q;
  cin >> n >> q;
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> depth(n), cnt(n), parent_at_depth(n, -1);
  bool siblings = true;
  int h = 0;
  auto dfs = [&](auto&& self, int u, int p) -> void {
    int d = depth[u];
    cnt[d]++;
    h = max(h, d);
    if (u != 0) {
      if (parent_at_depth[d] == -1) parent_at_depth[d] = p;
      if (parent_at_depth[d] != p) siblings = false;
    }
    for (int v : g[u]) {
      if (v == p) continue;
      depth[v] = d + 1;
      self(self, v, u);
    }
  };
  dfs(dfs, 0, -1);
  vector<int> fact(n + 1, 1);
  for (int i = 1; i <= n; i++) fact[i] = 1LL * fact[i - 1] * i % mod;
  int one = 1;
  for (int d = 0; d <= h; d++) {
    if (cnt[d] > 1) one = 0;
  }
  i64 two = siblings ? fact[cnt[h]] : 0;
  for (int d = 0; d < h; d++) two = two * fact[cnt[d] - 1] % mod;
  for (int i = 0; i < q; i++) {
    int k;
    cin >> k;
    cout << (k == 1 ? one : two) << ' ';
  }
  cout << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int T;
  cin >> T;
  while (T--) solve();
}

枚举排列并统计距离上限（通过子任务 1，共 8 分）

直接检查所有排列

本方法利用子任务 $1$ 的 $\sum N\le10$。先从每个顶点出发遍历一次树，得到所有点对的距离 $d(u,v)$；到顶点 $1$ 的距离就是根为 $1$ 时的深度。

枚举 $1,2,\ldots,N$ 的所有排列。逐项检查相邻顶点的深度是否非递减；若某处下降，则该排列对所有 $K$ 都不合法。若深度满足要求，记

$$m(p)=\max_{2\le i\le N}d(p_{i-1},p_i).$$

$N=1$ 时没有相邻点，定义 $m(p)=0$。这个排列恰好对所有 $K\ge m(p)$ 合法，因此只需让计数 $b_{m(p)}$ 增加 $1$，不必对每个询问重新枚举。

枚举结束后做前缀和，得到

$$f(K)=\sum_{j=0}^{K}b_j\pmod{10^9+7}.$$

每个排列恰好被枚举一次，深度检查和相邻距离最大值又直接对应题目的两个条件，所以既不会漏计，也不会重复。

复杂度

时间复杂度为 $O(N^2+N\cdot N!+Q)$：距离预处理为 $O(N^2)$，每个排列最多检查 $N-1$ 对相邻顶点。空间复杂度为 $O(N^2)$，主要用于点对距离表。

该方法只依赖小 $N$，不依赖 $K$ 的额外性质；大规模树上的阶乘枚举和平方距离表不再适用。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
  constexpr int mod = 1000000007;
  int n, q;
  cin >> n >> q;
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<vector<int>> dist(n, vector<int>(n));
  for (int s = 0; s < n; s++) {
    auto dfs = [&](auto&& self, int u, int p) -> void {
      for (int v : g[u]) {
        if (v == p) continue;
        dist[s][v] = dist[s][u] + 1;
        self(self, v, u);
      }
    };
    dfs(dfs, s, -1);
  }
  vector<int> ord(n), ans(n + 1);
  iota(ord.begin(), ord.end(), 0);
  do {
    bool ok = true;
    int cur = 0;
    for (int i = 1; i < n; i++) {
      if (dist[0][ord[i - 1]] > dist[0][ord[i]]) {
        ok = false;
        break;
      }
      cur = max(cur, dist[ord[i - 1]][ord[i]]);
    }
    if (ok) ans[cur] = (ans[cur] + 1) % mod;
  } while (next_permutation(ord.begin(), ord.end()));
  for (int k = 1; k <= n; k++) ans[k] = (ans[k] + ans[k - 1]) % mod;
  for (int i = 0; i < q; i++) {
    int k;
    cin >> k;
    cout << ans[k] << ' ';
  }
  cout << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int T;
  cin >> T;
  while (T--) solve();
}