可以把原题转换一下：初始边集为空，然后将 $n+k-2$ 条边按一个特定顺序以 $\dfrac{1}{2}$ 的概率加入边集。

连通块个数即为 $n$ 减去将两个连通块相连的边的数量。

如果第 $i$ 条边加入边集并且将两个连通块相连的概率为 $P_i$，那么答案就是 $n-\sum\limits_{i=1}^{n+k-2}P_i$。

考虑先处理 $n-1$ 条树边后处理 $k-1$ 条额外边。树边一定将两个连通块相连，所以对应的概率就是 $\dfrac{1}{2}$。

目前的答案就是 $n-(n-1)\times\dfrac{1}{2}=\dfrac{n+1}{2}$。

处理 $k-1$ 条额外边，注意到加入顺序是随意的，我们可以在两个叶子节点的 LCA 处理这条额外边。

令 $L_u$ 表示 $u$ 子树内 dfs 序最小的叶子节点，$R_u$ 表示 $u$ 子树内 dfs 序最大的叶子节点。

那么在 dfs 的过程中，我们当前的节点 $u$ 有两个相邻的儿子 $v,w$，我们就可以处理 $R_v$ 和 $L_w$ 之间的额外边。

设 $F_L(u)$ 表示 $u$ 和 $L_u$ 连通的概率；$F_R(u)$ 表示 $u$ 和 $R_u$ 连通的概率；

$F_{LR}(u)$ 表示 $L_u$ 和 $R_u$ 连通的概率；$D(u)$ 表示 $L_u$ 和 $R_u$ 连通，但不与 $u$ 连通的概率。

$F_{LR}(u)-D(u)$ 即 $u,L_u,R_u$ 连通的概率。

对于 $u$ 的第一个儿子 $v$：

1. $F_L(u)=\dfrac{1}{2}F_L(v),F_R(u)=\dfrac{1}{2}F_R(v)$，因为目前只有一个儿子，只能依靠当前树边连通。
2. $F_{LR}(u)=F_{LR}(v)$，因为这两个叶子节点的连通和当前树边无关。
3. $D(u)=\dfrac{1}{2}(F_{LR}(v)+D(v))$。

第一种情况：$L_v$ 和 $R_v$ 连通，但不与 $v$ 连通，概率为 $D(v)$

此时与当前树边无关，概率为 $D(v)$

第二种情况：$v,L_v,R_v$ 连通，概率为 $F_{LR}(v)-D(v)$

此时当前树边一定不能加进边集，概率为 $\dfrac{1}{2}(F_{LR}(v)-D(v))$

因此 $D(u)=D(v)+\dfrac{1}{2}(F_{LR}(v)-D(v))=\dfrac{1}{2}(F_{LR}(v)+D(v))$

对于 $u$ 后面的儿子 $v$：

1. 额外边对答案的贡献为 $-\dfrac1{2}[1-\dfrac{1}{2}F_R(u)F_L(v)]$

当前边有 $\dfrac{1}{2}$ 概率加进去，加进去后不影响答案需要满足 $u$ 和 $R_u$ 连通，$v$ 和 $L_v$ 连通，树边 $(u,v)$ 也存在。

1. $F^\prime_{L}(u)=F_{L}(u)+\dfrac{1}{4}D(u)F_L(v)$

第一种情况：原本 $u,L_u$ 就能连通，概率为 $F_L(u)$

第二种情况：$u,L_u$ 不连通

需要满足 $L_u,R_u$ 连通且不与 $u$ 连通，额外边 $(R_u,L_v)$ 存在，$L_v,v$ 连通，树边 $(u,v)$ 也存在，概率为 $\dfrac{1}{4}D(u)F_L(v)$。

1. $F^\prime_R(u)=\dfrac{1}{2}F_R(v)+\dfrac{1}{4}F_R(u)(F_{LR}(v)+D(v))$

注意新的 $R_u$ 是 $R_v$。

第一种情况：$v,R_v$ 连通并且树边 $(u,v)$ 存在，概率为 $\dfrac{1}{2}F_R(v)$。

第二种情况：$v,R_v$ 连通并且树边 $(u,v)$ 不存在

需要满足树边 $(u,v)$ 不存在， $L_v,R_v,v$ 都连通，额外边 $(R_u,L_v)$ 存在，$R_u,u$ 连通，概率为 $\dfrac{1}{4}F_R(u)(F_{LR}(v)-D(v))$。

第三种情况：$L_v,R_v$ 连通但不与 $v$ 连通，且树边 $(u,v)$ 不存在

还需要满足额外边 $(R_u,L_v)$ 存在，$R_u,u$ 连通，概率为 $\dfrac{1}{2}F_R(u)D(v)$。

$\begin{aligned}F^\prime_R(u)&=\dfrac{1}{2}F_R(v)+\dfrac{1}{4}F_R(u)(F_{LR}(v)-D(v))+\dfrac{1}{2}F_R(u)D(v)\\&=\dfrac{1}{2}F_R(v)+\dfrac{1}{4}F_R(u)(F_{LR}(v)+D(v))\end{aligned}$

1. $F^\prime_{LR}(u)=\dfrac{1}{2}(F_L(u)F_R(v)-D(u)D(v))+\dfrac{1}{4}(F_{LR}(u)+D(u))(F_{LR}(v)+D(v))$

注意新的 $R_u$ 是 $R_v$。

第一种情况是 $L_u$ 和 $u$ 连通，树边 $(u,v)$ 存在，$v,R_v$ 连通，概率为 $\dfrac{1}{2}F_L(u)F_R(v)$

第二种情况是 $L_u$ 和 $R_u$ 连通，额外边 $(R_u,L_v)$ 存在， $L_v$ 和 $R_v$ 连通，概率为 $\dfrac{1}{2}F_{LR}(u)F_{LR}(v)$

前两种情况有重复的，重复的满足：

$u,L_u,R_u$ 连通，$v,L_v,R_v$ 连通，树边 $(u,v)$ 存在，额外边 $(R_u,L_v)$ 存在，概率为 $\dfrac{1}{4}(F_{LR}(u)-D(u))(F_{LR}(v)-D(v))$

$\begin{aligned}F^\prime_{LR}(u)&=\dfrac{1}{2}F_L(u)F_R(v)+\dfrac{1}{2}F_{LR}(u)F_{LR}(v)-\dfrac{1}{4}(F_{LR}(u)-D(u))(F_{LR}(v)-D(v))\\&=\dfrac{1}{2}(F_L(u)F_R(v)-D(u)D(v))+\dfrac{1}{4}(F_{LR}(u)+D(u))(F_{LR}(v)+D(v))\end{aligned}$

1. $D^\prime(u)=\dfrac{1}{4}D(u)(F_{LR}(v)+D(v))$

注意新的 $R_u$ 是 $R_v$。由于 $L_u$ 一定不与 $u$ 连通，只能走额外边 $(R_u,L_v)$。

需要 $L_u,R_u$ 连通但不与 $u$ 连通，额外边 $(R_u,L_v)$ 存在，$L_v$ 和 $R_v$ 连通，概率为 $\dfrac{1}{2}D(u)F_{LR}(v)$。

但是不能同时满足 $L_v,R_v,v$ 连通且树边 $(u,v)$ 存在，概率为 $\dfrac{1}{4}D(u)D(v)$。

$D^\prime(u)=\dfrac{1}{2}D(u)F_{LR}(v)-\dfrac{1}{4}D(u)D(v)=\dfrac{1}{4}D(u)(F_{LR}(v)+D(v))$

时空 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100005,mod=998244353,inv2=(mod+1)>>1,inv4=(mod*3ll+1)/4;
int n,ans;
vector<int>vec[MAXN];
ll f[MAXN][4];//0: u,Lu; 1:u,Ru; 2:Lu,Ru; 3:Lu,Ru without u
void dfs(int u) {
    if(vec[u].empty()) {
        f[u][0]=f[u][1]=f[u][2]=1,f[u][3]=0;
        return;
    }
    for(int v:vec[u]) {
        dfs(v);
        if(v==vec[u][0]) {
            f[u][0]=f[v][0]*inv2%mod;
            f[u][1]=f[v][1]*inv2%mod;
            f[u][2]=f[v][2];
            f[u][3]=(f[v][2]+f[v][3])*inv2%mod;
        } else {
            ans=(ans+(1+f[u][1]*(mod-inv2)%mod*f[v][0])%mod*(mod-inv2))%mod;
            f[u][2]=(f[u][0]*f[v][1]+(mod-f[u][3])*f[v][3]+(f[u][2]+f[u][3])%mod*(f[v][2]+f[v][3])%mod*inv2)%mod*inv2%mod;
            f[u][0]=(f[u][0]+f[u][3]*inv2%mod*f[v][0]%mod*inv2)%mod;
            f[u][1]=(f[v][1]+f[u][1]*inv2%mod*(f[v][2]+f[v][3])%mod)*inv2%mod;
            f[u][3]=f[u][3]*inv4%mod*(f[v][2]+f[v][3])%mod;
        }
    }
}
void solve() {
    cin>>n;
    for(int i=1,x; i<=n; ++i) {
        cin>>x,vec[i].resize(x);
        for(int&x:vec[i])cin>>x;
    }
    ans=(n+1ll)*inv2%mod;
    dfs(1);
    cout<<ans<<endl;
}
int main() {
    cin.tie(0)->sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}