这个题数据水完了，建议大家自己自己随便拍两组，可能要比给的数据强。

有一个简单的做法，注意到对于一个节点 $u$，和他子树内所有关键点构成的集合 $S$，要么是 $u$ 能到达 $S$ 中的一些点，要么是 $S$  的一些点能到达 $u$，或者 $u,S$ 之间不连通。

直接设 $f_{i,0/1/2}$ 表示上面三种情况，做一个树上背包的合并即可，复杂度应该是 $O(n)$。

一个细节问题是对于关键点 $x$ 其 dp 的初始值如何处理，做法很多，但都能做到 $O(n)$。反正我写的很屎，但是 fhx 提供的很简洁（遗憾的是我没有理解）。

其实最开始我是往连通性方面想的 dp，结果最后想到了状态压缩上（？），于是在写错了一个很难写代码后，我短暂思考了另外一种很繁琐的做法，就是容斥。

先将边任意定向向都视为合法，然后减掉不合法的方案数，注意 $x\to y$ 和 $y\to x$ 这两种关系是不一样的，所以不合法的条件一共有 $k(k-1)$ 种。

枚举 $S$，求至少满足 $S$ 中所有不合法条件的方案数 $f(S)$，答案是 $\sum_{S}(-1)^{|S|}f(S)$，问题变成如何求答案。

暴力求是不行的，考虑树链剖分后用线段树维护，变成一个链覆盖的问题，可以做到 $O(k^2\log^2 n)$，最后的复杂度就是 $O(4^kk^2\log^2n)$，实际上因为复杂度省略了常数，容斥在 $k\le 4$ 的条件下可以轻松通过。

因为我用新加的数据测试了之前错的代码，所以给出的代码不保证对，但是这份代码是 fhx 的，应该是对的。

写题解纪念我们差点得到的金牌。

首先要发现怎么选才是最优的，显然深度靠下的点先走，让它走到一个自己能获得权值最大的叶子。

所以现在的问题就是对于一个点，该怎么快速求出它上面的那几个人能获得的最大权值。发现每次都是走到一个叶子，所以我们大概思路就是可以在每个点记录一下可能的路径数量，然后取前几个最优的（可以用set），并把剩下的丢进父亲节点的路径里，然后父亲再取，父亲合并儿子的路径的时候可以直接启发式合并，时间复杂度就是对的。

问题在于这样直接做可能两条优的路径里面有一些重叠的，答案就会大。解决方案其实也很简单，我们既然要避免一个点被算多次，那么就可以在算路径的时候只把自己的权值放进去一次，那么直接放进最优的路径就好。

然后随便写就过了，不开加速好像会超时。

fhx 跟我说这题是简单题我就一眼秒了，没想到意思发现了标解以外的在线算法。

假设 $n,q,V$ 同阶。

对 $a$ 分块，块长为 $B$，散块部分直接暴力计算，复杂度为 $O(B)$。

对于整块的部分，考虑对询问的 $k$ 进行阈值分治，令阈值也为 $B$，查询的整块区间为 $L\sim R$ 块。

若 $k\le B$，预处理 $f_{i,j}$ 表示 $1\sim i$ 块中所有数除以 $k$ 下取整之和，则这部分就是 $f_{R,k}-f_{L-1,k}$。

若 $k> B$，枚举 $v\in [0,\lfloor\frac{V}{k}\rfloor]$ 表示存在多少个 $\lfloor\frac{a_i}{k}\rfloor=v$ 在整块区间内，转化为查询多少个值域在 $[vB,(v+1)B)$ 的数在整块区间里面，预处理 $g_{i,j}$ 表示前 $i$ 块 $\le j$ 的数的个数，也可以 $O(1)$ 求。

直接取 $B=\sqrt{n}$ 可以得到理论最优复杂度为 $O(n\sqrt{n})$，空间为 $O(n\sqrt{n})$。实际上对于第二问转化出来的询问离线处理也可以做到空间线性。

别看我，代码是 ds 写的。

诈骗题说是，但话说真的有快速阶乘和算法说是，建议 $n\le 10^{18}$。

注意到 $i\ge 10000$ 时，$i!$ 必然能被 $10000$ 整除，后面的部分不用算即可，复杂度为 $O(1)$。

分析

构造方法是：

1.  对于每个点，随机选择一个比其标号小的点作为父亲，生成一棵**递增标号树**。

2. 对上述树的标号打乱。

不难想到，第一步产生的数则种类有 $\prod_{i=2}^{N} (i-1)$ 个，第二步的排列数有 $N!$ 个可能。所以，总方案数为：

$$\prod_{i=2}^{N} (i-1) \times N!$$

关键点来了：有多少种情况可以生成这个树。反向考虑这棵树能怎么生成，也就是存在一种情况得到了一个递增树和一个排列，可以得到这个树。显然，如果一个递增树可以加上某个排列形成这棵树，那么这个排列是唯一确定的。那么，任意一个与输入的树结构相同的递增标号树都可以得到这个树，做一个贡献。如何计算这个贡献？首先，由定义可知 `1` 号节点一定是根，令其 $k$ 个子节点的子树大小分别为 $s_1, s_2, \dots, s_k$，则每个子树分配点集方案树为

$$C_{n-1}^{s_1} \times C_{n-1-s_1}^{s_2} \times \dots \times C_{n-1-\sum_{i=1}^{k-1} s_i}^{s_k}$$

化简可得

$$\frac{N!}{s_1! \times s_2! \times \dots \times s_k!}$$

每个子树同样满足这个标号规则，令 $f(T)$ 为以 $T$ 为根的子树的方案，则：

$$f(T) = \frac{N!}{\prod s_i!} \times \prod f(子树i)$$

展开，化简可得：

$$f(T) = \frac{N!}{\prod sz_u}$$

其中，$sz_u$ 表示树上每个节点的子树大小。这样子我们可以求出来一个节点为根的方案树，接下来我们需要换根。

令 $f_u = \frac{N!}{\prod sz_x},\quad f_v = \frac{N!}{\prod sz'_x}$，从 $u$ 到 $v$ 只会有以下树改变：

$$sz_u = N,\quad sz_v = sz_v$$

$$sz_u' = N-sz_v,\quad sz_v'=N$$

分母产生的变化

$$D_u=(\prod_{x \ne u,v} sz_x) \times N \times sz_v$$

$$D_v = (\prod_{x\ne u,v} sz_x) \times (N-sz_v) \times N$$

比一下，

$$\frac{f_v}{f_u} = \frac{D_u}{D_v} = \frac{N \times sz_v}{(N-sz_v) \times N} = \frac{sz_v}{(N-sz_v)}$$

所以，$f_v = f_u \times \frac{sz_v}{(N-sz_v)}$。

之后我们将其求和，得到总答案数，再逆元除以总情况数即可。

参考代码

#include <cstring>
#include <iostream>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
int hd[N], nxt[N * 2], to[N * 2], num = 1;
void add(int u, int v) {
    num++;
    to[num] = v;
    nxt[num] = hd[u];
    hd[u] = num;
}
int sz[N];
void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}
long long fpow(long long x, long long y) {
    long long res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
int n;
long long f[N];
void dfs2(int u, int fa) {
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        f[v] = f[u] * sz[v] % mod * fpow(n - sz[v], mod - 2) % mod;
        dfs2(v, u);
    }
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        num = 1;
        memset(hd, 0, sizeof(hd));
        for (int i = 1; i <= n - 1; i++) {
            int u, v;
            cin >> u >> v;
            add(u, v);
            add(v, u);
        }
        dfs(1, 0);
        long long fz = 1;  // 分子
        for (int i = 1; i <= n; i++) {
            fz = fz * i % mod;
        }
        long long fm = 1;  // 分母
        for (int i = 1; i <= n; i++) {
            fm = fm * sz[i] % mod;
        }
        f[1] = fz * fpow(fm, mod - 2) % mod;
        dfs2(1, 0);
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += f[i];
            ans %= mod;
        }
        fm = 1;
        for (int i = 1; i <= n - 1; i++) fm = fm * i % mod;
        for (int i = 1; i <= n; i++) fm = fm * i % mod;
        cout << ans * fpow(fm, mod - 2) % mod << endl;
    }
    return 0;
}