1106

我们来考虑一种特殊情况,树的结构是都是父亲指向儿子的情况。

进一步考虑节点 $x$ 合法的情况。

考虑其合法概率,即要在子节点被选择之前选择 $x$ 。

那么也就是 $\frac{1}{siz_x}$ ,这个应该不难得到,然后就可以进一步求解答案了。

然后我们考虑一条边 $(x,y)$ 反向的情况。

这里容斥处理一下,

因为反向边的贡献相当于 $x,y$ 两部分独立合法的贡献减去正向边的贡献。

之后我们就有一个 $dp$ 了。

$dp_{i,j}$ 表示以 $i$ 为根,$i$ 所处连通块 (因为独立合法和正向边所构成块的大小是不一样的) 大小为 $j$ 的概率。

$\sum_j dp_{i,j}$ 即为以 $i$ 为根的子树内所有节点都合法的概率 。

转移十分简单,就按照上面的容斥处理一下即可。

il int add(int a, int b) {return a += b, a >= mod ? a - mod : a;}
il int sub(int a, int b) {return a -= b, a < 0 ? a + mod : a;}


struct edge {
    int y, next, w;
} a[N << 1]; int len, last[N];

void ins(int x, int y, int w) {
    a[++len] = (edge) {y, last[x], w}; last[x] = len;
} 

int f[N][N], inv[N], siz[N], tmp[N];

void dfs(int x, int fa) {
    f[x][1] = 1; siz[x] = 1;
    for (int k = last[x], y; k; k = a[k].next) {
        y = a[k].y; if (y == fa) continue;
        dfs(y, x);
        rep (i, 1, siz[x]) 
            rep (j, 1, siz[y]) {
                int res = 1ll * f[x][i] * f[y][j] % mod;
                if (a[k].w == -1) tmp[i + j] = sub(tmp[i + j], res), tmp[i] = add(tmp[i], res);
                else tmp[i + j] = add(tmp[i + j], res);  
            }
        siz[x] += siz[y];
        rep (i, 1, siz[x]) f[x][i] = tmp[i], tmp[i] = 0;
    } rep (i, 1, siz[x]) f[x][i] = 1ll * f[x][i] * inv[i] % mod;
    
}

void solve() {
    int n; qr(n);
    inv[1] = 1; rep (i, 2, n) inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
    rep (i, 1, n - 1) {
        int x, y; qr(x), qr(y);
        ins(x, y, 1); ins(y, x, -1);    
    } dfs(1, 0);
    int ans = 0;
    rep (i, 1, n) ans = add(ans, f[1][i]);
    rep (i, 1, n) ans = 1ll * ans * i % mod;
    pr2(ans); 
}