まず、良い木が存在するための必要十分条件は \(\displaystyle \sum_{i=1}^{N} X_i = 2N-2\) です。

良い木が存在するとき、その直径の最大値を考えましょう。直径に含まれる頂点は両端点を除いて次数が \(2\) 以上であることから、次数が \(2\) 以上の頂点の個数を \(K\) としたとき、\(K+1\) は解の上界です。逆に、直径が \(K+1\) となる良い木が必ず存在します。具体的には、

• \(X_i\geq 2\) を満たす頂点 \(i\) たちを適当な順序で一列に並べて、隣接する頂点間に辺を張ることでパスを作る
• 「\(X_i\geq 2\) を満たす頂点 \(i\) であって、次数が \(X_i\) に満たないものがあるならば、\(X_j=1\) を満たしまだ辺が張られていない頂点 \(j\) を \(1\) つ持ってきて、頂点 \(i,j\) の間に辺を張る」ことを繰り返す (\(\displaystyle \sum_{i=1}^{N} X_i = 2N-2\) より、この操作は \(X_j=1\) を満たす頂点 \(j\) をちょうど使い切る)

ことで構築できます (ヒントの図も参考にしてください)。よって、良い木が存在するような \(X\) の集合を \(S\) とすると、

\(\begin{aligned} \sum_{X\in S} f(X) &= \sum_{X\in S} ((X\ \text{に含まれる 2 以上の整数の個数}) +1)\\ &= |S| + \sum_{X\in S} (X\ \text{に含まれる 2 以上の整数の個数})\\ &= |S| + \sum_{i=1}^{N} (X_i\geq 2\ \text{を満たす}\ X \in S\ \text{の個数})\\ &=|S|+(X_1\geq 2\ \text{を満たす}\ X \in S\ \text{の個数})\times N\\ &=(\sum_{i=1}^{N} X_i = 2N-2\ \text{を満たす正整数列}\ X\ \text{の個数})+(\sum_{i=1}^{N} X_i = 2N-2\land X_1\geq 2\ \text{を満たす正整数列}\ X\ \text{の個数})\times N\\ &=(\sum_{i=1}^{N} X_i = N-2\ \text{を満たす非負整数列}\ X\ \text{の個数})+(\sum_{i=1}^{N} X_i = N-3\ \text{を満たす非負整数列}\ X\ \text{の個数})\times N\\ &= \binom{(N-2)+(N-1)}{N-1}+\binom{(N-3)+(N-1)}{N-1}\times N\\ &= \binom{2N-3}{N-1}+\binom{2N-4}{N-1}\times N \end{aligned}\)

となるため、階乗とその逆元の値を前計算しておくことで、\(1\) テストケースあたり \(O(1)\) でこの問題を解くことができます。

想定解 (C++) :

#include<bits/stdc++.h>
#include<atcoder/modint>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

const int C = 2000010;
vector<mint> fact(C), ifact(C);

mint binom(int n, int k) {
    if (k < 0 or k > n) return 0;
    return fact[n] * ifact[k] * ifact[n - k];
}

int main() {
    fact[0] = 1;
    for (int i = 1; i < C; i++) fact[i] = fact[i - 1] * i;
    ifact[C - 1] = fact[C - 1].inv();
    for (int i = C - 2; i >= 0; i--) ifact[i] = ifact[i + 1] * (i + 1);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        mint ans = binom(2 * n - 3, n - 1) + binom(2 * n - 4, n - 1) * n;
        cout << ans.val() << '\n';
    }
}