First of all, a good tree exists if and only if \(\displaystyle \sum_{i=1}^{N} X_i = 2N-2\).

Let us find the maximum diameter when a good tree exist. Since every degree of the vertices in the diameter, except for the endpoints, is at least \(2\), so the \((K+1)\) is the upper bound of the solution, where \(K\) is the number of vertices whose degrees are at least two. Conversely, there is a good tree whose diameter is \((K+1)\). Specifically, the tree can be constructed by:

• first lining up the vertices \(i\) such that \(X_i\geq 2\) in a line, constructing a path adding edges in between,
• then repeatedly, while there is a vertex \(i\) such that \(X_i\geq 2\) but the degree does not reach \(X_i\), finding a vertex \(j\) such that \(X_j=1\) but does not have an incident edge, and adding an edge between vertices \(i\) and \(j\). (Since \(\displaystyle \sum_{i=1}^{N} X_i = 2N-2\), this operation uses up the vertices \(j\) such that \(X_j=1\).)

(See also the figure in the hint.) Therefore, denoting by \(S\) the set of \(X\) that yields a good tree, we have

\(\begin{aligned} \sum_{X\in S} f(X) &= \sum_{X\in S} ((\text{the number of integers at least two in }X) +1)\\ &= |S| + \sum_{X\in S} (\text{the number of integers at least two in }X)\\ &= |S| + \sum_{i=1}^{N} (\text{The number of }X \in S\text{ such that }X_i\geq 2)\\ &=|S|+(\text{The number of }X \in S\text{ such that }X_i\geq 2)\times N\\ &=(\text{The number of sequences of positive integers }X\text{ such that }\sum_{i=1}^{N} X_i = 2N-2)+(\text{The number of sequences of positive integers }X\text{ such that }\sum_{i=1}^{N} X_i = 2N-2\land X_1\geq 2)\times N\\ &=(\text{The number of sequences of non-negative integers }X\text{ such that }\sum_{i=1}^{N} X_i = N-2)+(\text{The number of sequences of non-negative integers }X\text{ such that }\sum_{i=1}^{N} X_i = N-3)\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}\)

Thus, by precalculating the factorials and their inverses, the problem can be solved in an \(O(1)\) time per case.

Writer’s solution (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';
    }
}