link

题目大意：

n个节点的带标号无根树。每次选择一个度数为1的节点并将它从树上移除。问总共有多少种不同的方式能将这棵树删到只剩 1 个点。两种方式不同当且仅当至少有一步被删除的节点不同。

题解：

先考虑1号店最后移除时候的贡献，我们可以钦定1号点为根，并钦定他最后移除

然后就是一个树形dp

设\(f_i\)表示i号点子树移除方案数量，\(size_i\)表示1为根时子树大小

显然有dp式子\(f_x=\frac{(size_x-1)!}{\prod (size_i)!}\prod f_i\) (满足1为根时x是i的爹)

然后最后移除点1的情况的贡献就算出来了

我们考虑换根

先考虑x的转移少了j这个子树节点会咋样

那么\(f'_x=f_x/f_j/(size_x-1)!*(size_x-1-size_j)!*(size_j)!\)

注意这里的\(size_x\)是n，我们已经假设x是树的根了

然后我们再把\(f'_x\)转移到j上去，则新的j有

\(f'_j=f_j*f'_x/(size_j-1)!*(n-1)!/(n-size_i)!\)

由于涉及到求逆元，时间复杂度为\(O(n\log n)\)

#include <cstdio>

#include <vector>

using namespace std;

const int xkj = 998244353;

int n;

vector<int> out[100010];

int sz[100010], fa[100010], f[100010];

int fac[100010], inv[100010], ans;

int qpow(int x, int y)

{

	int res = 1;

	for (x %= xkj; y > 0; y >>= 1, x = x * (long long)x % xkj)

		if (y & 1) res = res * (long long)x % xkj;

	return res;

}

void dfs1(int x)

{

	sz[x] = 1, f[x] = 1;

	for (int i : out[x]) if (fa[x] != i)

	{

		fa[i] = x, dfs1(i), sz[x] += sz[i];

		f[x] = f[x] * (long long)f[i] % xkj;

		f[x] = f[x] * (long long)inv[sz[i]] % xkj;

	}

	f[x] = f[x] * (long long)fac[sz[x] - 1] % xkj;

}

void dfs2(int x)

{

	ans = (ans + f[x]) % xkj;

	for (int i : out[x]) if (fa[x] != i)

	{

		int tmp = f[x] * (long long)qpow(f[i], xkj - 2) % xkj * fac[sz[i]] % xkj * inv[n - 1] % xkj * fac[n - 1 - sz[i]] % xkj;

		int sb = f[i] * (long long)tmp % xkj * inv[sz[i] - 1] % xkj * fac[n - 1] % xkj * inv[n - sz[i]] % xkj; f[i] = sb;

		dfs2(i);

	}

}

int main()

{

	scanf("%d", &n);

	fac[0] = 1;

	for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * (long long)i % xkj;

	inv[n] = qpow(fac[n], xkj - 2);

	for (int i = n; i >= 1; i--) inv[i - 1] = inv[i] * (long long)i % xkj;

	for (int x, y, i = 1; i < n; i++) scanf("%d%d", &x, &y), out[x].push_back(y), out[y].push_back(x);

	dfs1(1), dfs2(1);

	printf("%d\n", ans);

	return 0;

}