这里提供一种比老师思路简单，但是数学计算量大一（亿）点点的题解

前置芝士：组合数学有关内容

solution

首先翻译下题面，找出所有长度为 $n$ 的序列 X：满足存在一颗树，使得树的每个顶点 $i$ 度数为 $x_i$，同时最大化树的直径。求出所有长度为 $n$ 的序列 X 的树的直径之和

首先，容易发现一个性质：

$$\sum_{i = 1}^n{x_i} = 2n - 2$$

即节点的度数之和为 $2$ 倍的边数

其次，$x_i \geq 1$，根据这两个性质可以推导出对于序列 X，其形成的好树直径最大为：

$$d = \sum_{i = 1}^n{[x_i > 1]} + 1$$

其中[]运算符 []内为真结果是 $1$，否则为 $0$

解释下这个式子，我们可以让所有的度数大于 1 的节点构成一条链，然后叶节点就挂在链上即可，链的直径显然为链上的节点数加 $1$

有了这个结论后就可以枚举叶节点的个数，显然叶节点的个数不同树的最大直径也就不同，设叶节点的个数为 $k$ , 则直径为 $(n - k + 1)$。那么我们现在的问题就是求出叶节点个数为 $k$ 时所有序列 X 的个数

因为叶节点个数为 $k$ , 占用了 $k$ 个度数，其他节点的个数为 $n - k$，占用了 $2n - 2 - k$ 个度数，于是问题等价为有 $2n - 2 - k$ 个球放在 $n - k$ 个箱子中的方案数，因为一个箱子内不能只放一个球，所以我们在所有箱子中放一个球，由隔板法知总方案有：

$$\begin{split} cnt &= \binom {2n - 2 - k - (n - k) - 1} {n - k - 1}\\ &=\binom {n - 3} {n - k - 1}\end{split}$$

由于叶节点有 $k$ 个，所以一共有 $\binom nk$ 种选择叶节点的方案，根据乘法原理，再考虑上直径有：

$$ans = \sum_{k = 1}^n \binom nk \binom {n - 3} {n - k - 1}(n-k+1)$$

显然，直接处理是 $O(n)$ 的，会超时，所以到了我们愉快（痛苦）的推柿子时间啦！

在推式子之前，需要两个前置等式：

1. 吸收恒等式:

$$k\binom nk = n\binom{n - 1}{k - 1}$$

证明如下：

$$\begin{split} k\binom nk &= k {n! \above 1pt(n - k)!k!}\\ &= {n! \above 1pt(n - k)!(k - 1)!} \end{split}$$$$\begin{split} n\binom{n - 1}{k - 1} &= n {(n - 1)! \above 1pt(n - k)!(k - 1)!}\\ &= {n! \above 1pt(n - k)!(k - 1)!} \end{split}$$

的证

2. 范德蒙德卷积:

$$\sum_{i = 0}^k{\binom ni \binom m{k - i}} = \binom {n + m}k$$

证明如下：

考虑原式的实际含义，在 $n + m$ 个数中选 $k$ 个显然等于在 $n$ 个数中选 $i$ 个再到 $m$ 个数中选 $k - i$ 个，再根据加法原理，将结果组合起来即可

推式子时间！（虽然看上去比较复杂，但实际还是不难的 awa）

$$\begin{split} ans &= \sum_{k = 1}^n \binom nk \binom {n - 3} {n - k - 1}(n-k+1) \\ &= \sum_{k = 1}^n \binom nk \binom {n - 3} {n - k - 1}(n - k - 1 + 2) \\ &= \sum_{k = 1}^n \binom nk \binom {n - 3} {n - k - 1}(n - k - 1) + 2\sum_{k = 1}^n \binom nk \binom {n - 3} {n - k - 1} \\ &= \sum_{k = 1}^n \binom nk \binom {n - 4} {n - k - 2}(n - 3) + 2\sum_{k = 1}^n \binom nk \binom {n - 3} {n - k - 1} \\ &= (n - 3) \sum_{k = 1}^n \binom nk \binom {n - 4} {n - 2 - k} + 2\sum_{k = 1}^n \binom nk \binom {n - 3} {n - 1 - k} \\ &= (n - 3)\binom{2n - 4}{n - 2} + 2 \binom {2n-3}{n-1} \end{split}$$

可见我们已经推到为组合数的形式，所以可以先预处理出组合数，再直接算即可，注意大数除法要用乘法逆元处理

时间复杂度：$O(T + n)$

code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e6 + 5;
const int mod = 998244353;

int t , n;
int inv[N + 5] , mul[N + 5];

int kmi(int a , int b){
	int res = 1;
	
	while(b){
		if(b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b /= 2;
	}
	return res % mod;
}

int C(int n , int m){
	if(n < m || n < 0 || m < 0) return 0;                                      // c_n^m
	return mul[n] * (inv[n - m] * inv[m] % mod) % mod;
}

signed main(){
	freopen("F.in" , "r" , stdin);
	freopen("F.out" , "w" , stdout);
	
	cin >> t;
	
	mul[0] = 1;
	for(int i = 1 ; i < N ; i ++){
		mul[i] = (i * mul[i - 1]) % mod;
	}
	inv[N - 1] = kmi(mul[N - 1] , mod - 2);
	for(int i = N - 1 ; i >= 0 ; i --){
		inv[i - 1] = (inv[i] * i) % mod;
	}
	
	while(t --){
		cin >> n;
		
		int tmp1 = ((n - 3) * C(2 * n - 4 , n - 2) % mod) % mod;
		int tmp2 = (2 * C(2 * n - 3 , n - 1) % mod) % mod;
		cout << (tmp1 + tmp2) % mod << endl;
	}
	return 0;
}

希望此题解能帮助到你 $qwq$