先考虑一个序列的贡献，
一个序列 \(X\) 要满足存在对应的树的充要条件是 \(\sum X_i =2N-2\)。
如何构造一棵直径最长的树？不妨令根节点度数为 \(1\)，每次可以在当前最深的点下接上一个非叶子节点，使最长链延长，再算上链的末尾的一个叶子节点，记序列中大于 \(1\) 的数的数量为 \(k\)，序列的贡献为 \(k+1\)。
比如，对于序列 \([4,3,2,1,1,1,1,1]\) 可以这样构造 \(\darr\)。
O|O/ \O O/|\O O O|O
于是可以枚举序列中大于 \(1\) 的数量 \(k\) ，统计这样的序列的数量：
- 选择 \(k\) 个位置不为 \(1\)，方案数为 $C_n^k $。
- 接下来需要满足 \(\sum X_i =2N-2,\sum(X_i-1)=n-2\)。只考虑原来大于 \(1\) 的数 \(x_1,x_1,\dots,x_k,x_i=X_i-2\)，即 \(x_i\geq 0\)；需要求方程 \(x_1+x_2+\dots+x_k=N-k-2\) 的非负整数解数量，使用插板法，解的数量即为 \(C_{(N-k-2)+(k-1)} ^ {k-1}=C_{N-3}^{k-1}\)。
\[\begin{aligned}
ans &= \sum_{k=1}^{N-2} (k+1)C_N^k C_{N-3}^{k-1} \\&= \sum_{k=1}^{N-2}kC_N^k C_{N-3}^{k-1}+\sum_{k=1}^{N-2}C_N^k C_{N-3}^{k-1} \\
\end{aligned}
\]
由 \(kC_r ^k =rC_{r-1}^{k-1}\)(直接展开可证明)，可知，
\[\begin{aligned}
ans &= N\sum_{k=1}^{N-2}C_{N-1}^{k-1} C_{N-3}^{k-1}+\sum_{k=1}^{N-2}C_N^k C_{N-3}^{k-1} \\&= N\sum_{k=0}^{N-3}C_{N-1}^{k} C_{N-3}^{k}+\sum_{k=0}^{N-2}C_N^k C_{N-3}^{k-1} \\&= N\sum_{k=0}^{N-3}C_{N-1}^{k} C_{N-3}^{N-k-3}+\sum_{k=0}^{N-2}C_N^k C_{N-3}^{N-k-2} \\
\end{aligned}
\]
由 \(\sum_{i=0}^{x}C_n^iC_m^{x-i}=C_{n+m}^x\)(由组合意义可证明)，可知，
\[\begin{aligned}
ans &= NC_{2N+4}^{N-3}+C_{2N-3}^{N-2} \\
\end{aligned}
\]
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353,N=2000000;
ll T,n,jc[N+6],ijc[N+6],ans;
inline ll qpow(ll a,ll b){ll ret=1;while(b){if(b&1)ret=ret*a%mod;a=a*a%mod;b>>=1;}return ret;
}
inline ll C(ll m,ll n){if(m<0)return 0;return 1ll*jc[n]*ijc[m]%mod*ijc[n-m]%mod;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);jc[0]=ijc[0]=1;for(ll i=1;i<=N;i++)jc[i]=1ll*jc[i-1]*i%mod;ijc[N]=qpow(jc[N],mod-2);for(ll i=N-1;i>=1;i--)ijc[i]=1ll*ijc[i+1]*(i+1)%mod;cin>>T;while(T--){cin>>n;ans=1ll*(n*C(n-3,2*n-4)%mod+C(n-2,2*n-3))%mod; cout<<ans<<"\n";}return 0;
}