[UOJ#351]新年的叶子

试题描述

躲过了AlphaGo 之后，你躲在 SingleDog 的长毛里，和它们一起来到了AlphaGo 的家。此时你们才突然发现，AlphaGo 的家居然是一个隐藏在地下的计算中心！难道 AlphaGo 如此人赢的秘密是...它其实是一个 AI？

根据情报，这个地下的计算中心的结构构成了一棵无根树，整个计算中心名为被 AT-field 的力场保护起来，保护力场的直径恰好等于树的直径（树的直径定义为树上距离最远的两个结点之间的距离，结点 (u,v) 的距离定义为从 (u) 到 (v) 最少需要经过的边数）。

由于保护力场的存在，SingleDog 们每次只能进入整棵树的一个叶子（度为 (1) 的结点），由于狗的大脑很小，他们每次只会随机进攻一个原树的叶子，并且破坏里面的设备，更加狼狈的是他们甚至会重复进入一个已经被破坏过的叶子。

QAQ

比如这棵树中，SingleDog 们攻击的就是 (3,4,7) 这三个点，他们不会攻击 (2) 号点，因为它不是原树的叶子。

他们想知道，期望多少次之后，可以使得保护力场的直径缩小？

即，对于一棵树，每次随机染黑一个叶子（可能会重复染黑），期望多少次后直径变小？

输入

从标准输入读入数据。

第一行一个正整数 (n)，表示树的点数。

接下来 (n−1) 行，每行两个正整数 (x,y)，表示树上的一条边。

输出

输出到标准输出。

输出一行一个整数表示答案在模 (998244353) 意义下的取值。

即设答案化为最简分式后的形式为 (frac{a}{b}) ，其中 (a) 和 (b) 互质。输出整数 (x) 使得 (bx equiv a(mod 998244353)) 且 (0 le x < 998244353)。可以证明这样的整数 (x) 是唯一的。

输入示例1

3
1 2
2 3

输出示例1

输入示例2

输出示例2

499122178

数据规模及约定

对于所有数据，(3 le n le 5 imes 10^5)，(1 le x,y le n)。

题解

首先考虑一下直径的性质，若直径长度为偶数条边，所有直径的中点是相同的；否则所有直径最中间那条边是相同的。

令 (l) 为直径长度。

那么对于偶数的情况，我们将 (u) 的每个儿子中深度为 (frac{l}{2}) 的所有叶子放在一个集合当中，这样当染到只有一个集合内还有未被染黑的叶子时直径一定变短了；

若 (l) 为奇数，那么所有深度为 (frac{l+1}{2}) 的叶子一定在同一个子树中，把所有不在那个子树中的深度为 (frac{l-1}{2}) 的叶子放到一个集合中就可以按照和偶数情况一样处理了。

现在需要把问题转化一下，把“每次可以染黑点”改成“每次一定染白点”，但是这样改之后每一步的期望不再是 (1) 了，所以我们令这个期望是 (x)，然后尝试计算出来。

具体来说，现在有 (n) 个叶子，有 (m) 个白的，其余都是黑的，那么染一个白色叶子需要期望多少步。考虑下一步染色的两种情况，分别是染黑色叶子和染白色叶子，两种情况概率分别是 (frac{n-m}{n}) 和 (frac{m}{n})，如果染白色叶子那么目标已经完成，所以期望步数是 (1)，否则相当于没做任何操作，所以期望步数还是 (x)，所以我们可以列一个方程

[x = frac{n-m}{n}x + frac{m}{n} ]

解得 (x = frac{n}{m})。

现在我们枚举集合 (x)，假装它最终没有被染黑（即忽略掉它），在这种情况下染黑其它所有集合中的节点的期望步数是多少？很显然就是每一步的期望的叠加，令 (N) 表示总叶子数，(S) 表示所有集合中叶子的总数，期望步数就是 (sum_{i=1}^{S - |x|} frac{N}{i})，这里就是将关系的点看成白色，忽略的点看成黑色。

如果我们将对于所有 (x) 的这个期望直接累加肯定不是答案，它算多了。这是因为我们那么算期望步数的时候并没有考虑集合 (x) 内的叶子的染色情况，也就是说它们被全部染黑的情况也被统计进去了；所以我们多算的部分就是所有集合中的叶子都染黑的情况。注意到只有在最后一步染黑的集合不是 (x) 的时候才会多算，也就是说在枚举到集合 (x) 的时候我们多算的是 (sum_{y e x} 最后一步将集合 y 染黑，使得所有集合中的叶子全黑的期望步数)。那么多算的部分就是（令集合个数为 (T)，(E(y)) 表示“最后一步将集合 (y) 染黑，使得所有集合中的叶子全黑的期望步数”）

[sum_x sum_{y e x} E(y) \ = sum_y E(y) sum_{x e y} 1 \ = sum_y E(y) cdot (T - 1) \ = (T - 1) sum_y E(y) ]

所以多算的就是 ((T-1)) 倍的将所有集合中的叶子染黑的期望步数，最后减去这个数就好了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxn 500010
#define maxm 1000010
#define MOD 998244353
#define LL long long

int n, m, head[maxn], nxt[maxm], to[maxm], deg[maxn];

void AddEdge(int a, int b) {
	to[++m] = b; nxt[m] = head[a]; head[a] = m;
	swap(a, b);
	to[++m] = b; nxt[m] = head[a]; head[a] = m;
	deg[a]++; deg[b]++;
	return ;
}

int step[maxn], fa[maxn], Q[maxn], hd, tl;
int BFS(int s) {
	memset(step, -1, sizeof(step));
	hd = tl = 0; Q[++tl] = s; step[s] = 0; fa[s] = 0;
	while(hd < tl) {
		int u = Q[++hd];
		for(int e = head[u]; e; e = nxt[e]) if(step[to[e]] < 0) {
			step[to[e]] = step[u] + 1;
			fa[to[e]] = u;
			Q[++tl] = to[e];
		}
	}
	int mx = 0, mxi;
	rep(i, 1, n) if(step[i] > mx) mx = step[i], mxi = i;
	return mxi;
}

int mxh[maxn], tot[maxn];
void dp(int u, int pa) {
	mxh[u] = 0; tot[u] = 1;
	for(int e = head[u]; e; e = nxt[e]) if(to[e] != pa) {
		dp(to[e], u);
		if(mxh[to[e]] + 1 == mxh[u]) tot[u] += tot[to[e]];
		else if(mxh[to[e]] + 1 > mxh[u]) mxh[u] = mxh[to[e]] + 1, tot[u] = tot[to[e]];
	}
	return ;
}

int siz[maxn], cnts, inv[maxn], sum[maxn];

int main() {
	n = read();
	rep(i, 1, n - 1) {
		int a = read(), b = read();
		AddEdge(a, b);
	}
	
	int A = BFS(1), B = BFS(A), len = step[B];
	rep(i, 1, len >> 1) B = fa[B];
	dp(B, 0);
	for(int e = head[B]; e; e = nxt[e]) if(mxh[to[e]] + 1 == (len + 1 >> 1)) siz[++cnts] = tot[to[e]];
	if(len & 1) {
		cnts++;
		for(int e = head[B]; e; e = nxt[e]) if(mxh[to[e]] + 1 == (len >> 1)) siz[cnts] += tot[to[e]];
	}
	
	int N = 0, sn = 0;
	rep(i, 1, n) N += deg[i] == 1;
	rep(i, 1, cnts) sn += siz[i];
	inv[1] = 1;
	rep(i, 2, N) inv[i] = (LL)(MOD - MOD / i) * inv[MOD%i] % MOD;
	sum[0] = 0;
	rep(i, 1, n) {
		sum[i] = sum[i-1] + (LL)N * inv[i] % MOD;
		if(sum[i] >= MOD) sum[i] -= MOD;
	}
	
	int ans = 0;
	rep(i, 1, cnts) {
		ans += sum[sn-siz[i]];
		if(ans >= MOD) ans -= MOD;
	}
	ans -= (LL)(cnts - 1) * sum[sn] % MOD;
	if(ans < 0) ans += MOD;
	
	printf("%d
", ans);
	
	return 0;
}