题目大意

给定以 $1$ 为根结点的一棵树，有 $n(n\leq5\times10^5)$ 个节点，对于每个 $k\leq n$ ，求随机选取 $k$ 的结点的期望 LCA 深度，结果对 998244353 取模。

题解

考虑每个点 $u$ 的贡献为

$$\text{dep}(u)\left(\binom{|T_u|}{k}-\sum_{v\in\text{son}(u)}\binom{|T_v|}{k}\right) $$

注意到，子结点的深度是当前深度的后继，故对于一个 $k$ ，答案为

$$\frac{1}{\binom{n}{k}}\sum_{u=1}^n \binom{|T_u|}{k} $$

考虑优化。

二项式系数自带一个卷积的形式，考虑写成多项式的形式。记子树大小为 $|T_u|$ 的子树数量为 $a_i$ ，有

$$\sum_k \frac1{k!}\left(\sum_ia_ii!\cdot\frac1{(i-k)!}\right) $$

令 $j=i-k$ ，上式就是 $i-j=k$ 的减法卷积形式。减法卷积相当于 $i+(-j)$ ，负数下标对 $n$ 取模，即 $n-j$ ，也可以看作是翻转数组，然后平移。

代码

const int N = 5e5 + 10, pN = N << 3, mod = 998244353;
const int G = 3, invG = 332748118;
 
ll read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}
 
int add(int a, int b) { return a + b > mod? a + b - mod: a + b; }
int dec(int a, int b) { return a > b? a - b: a - b + mod; }
int mul(int a, int b) { return 1ll * a * b % mod; }
#define clr(f, x) memset(f, 0, sizeof(int) * (x))
#define cpy(f, g, x) memcpy(f, g, sizeof(int) * (x))
 
namespace Main {
	int n;
	struct edge {
		int to, nxt;
	} e[N << 1];
	int head[N], tot;
	void add_edge (int u, int v) { e[++tot] = (edge) {v, head[u]}; head[u] = tot; }
 
	int siz[N];
	void dfs (int u, int fa) {
		siz[u] = 1;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (fa == v) continue;
			dfs(v, u); siz[u] += siz[v];
		}
	}
 
	int fac[N], ifac[N];
	int qpow (int a, ll b) {
		int ans = 1;
		for (; b; b >>= 1, a = mul(a, a))
			if (b & 1) ans = mul(ans, a);
		return ans;
	}
	int binom(int n, int m) {
		if (n < m) return 0;
		return mul(fac[n], mul(ifac[m], ifac[n - m]));
	}
 
	int cnt[N];
	int f[pN], g[pN];
 
	struct poly {
		int tr[pN];
		
		void init(int n, int siz) {
			for (int i = 0; i < n; ++i)
				tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (siz - 1));
		}
 
		void NTT(int *f, int n, int op = 1) {
			for (int i = 0; i < n; ++i) 
				if (i < tr[i]) swap(f[i], f[tr[i]]);
			for (int p = 1; p < n; p <<= 1) {
				int omega = qpow(op? G: invG, (mod - 1) / (p << 1));
				for (int j = 0; j < n; j += p << 1) 
					for (int w = 1, k = 0; k < p; k++, w = mul(w, omega)) {
						int x = f[j | k], y = mul(w, f[j | p | k]);
						f[j | k] = add(x, y), f[j | p | k] = dec(x, y);
					}
			}
			if (!op) {
				int invn = qpow(n, mod - 2);
				for (int i = 0; i < n; ++i) f[i] = mul(f[i], invn);
			}
		}
		void times(int *f, int *g, int n, int m, int T) {
			int lim = 1, lsiz = 0; for (; lim < n + m; lim <<= 1, lsiz++);
			init(lim, lsiz);
			static int tmp[pN]; clr(f + n, lim - n), cpy(tmp, g, m), clr(tmp + m, lim - m);
			NTT(f, lim); NTT(tmp, lim);
			for (int i = 0; i < lim; ++i) f[i] = mul(f[i], tmp[i]);
			NTT(f, lim, 0); 
			clr(f + T, lim - 1), clr(tmp, lim);
		}
	}p;
	
	int main () {
		n = read();
		for (int i = 1; i < n; ++i) {
			int u = read(), v = read();
			add_edge(u, v); add_edge(v, u);
		}
		dfs (1, 0);
		for (int i = 1; i <= n; ++i) ++cnt[siz[i]];
		fac[0] = 1;
		for (int i = 1; i <= N - 10; ++i) fac[i] = mul(fac[i - 1], i);
		ifac[N - 10] = qpow(fac[N - 10], mod - 2);
		for (int i = N - 10; i; --i) ifac[i - 1] = mul(ifac[i], i);
 
		int m = n + 1;
		for (int i = 0; i < m; i++) {
			f[i] = mul(cnt[i], fac[i]);
			g[i] = ifac[m - i - 1];
		}
 
		p.times(f, g, m, m, m << 1);
 
		for (int i = 0; i <= m; i++) f[i] = f[i + m - 1];
 
 
		for (int k = 1; k <= n; ++k) {
			int ans = qpow(binom(n, k), mod - 2);
			//int ans = 1;
			ans = mul(ans, ifac[k]);
			ans = mul(ans, f[k]);
			printf ("%d ", ans);
		}
		puts("");
		return 0;
	}
}
 
int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}