I · Island：中文题面与个人代码

时限 2 秒，内存限制 512 MB。中文内容依据本次提供的题面整理；以原题为准。

中文题面 #

给定一棵根为 $1$ 的有序有根树：每个结点的儿子有固定的从左到右顺序，根至少有两个儿子。按这个顺序 DFS，设依次首次访问的叶子为 $p_1,\ldots,p_k$ ；叶子指度为一的顶点，根不是叶子。

除了原树的 $n-1$ 条边，再连接连续叶子 $(p_i,p_{i+1})$ ， $1\le i<k$ 。叶子连成一条链，不连接首尾叶子，总边数为 $n+k-2$ 。

每条边独立地以 $1/2$ 的概率保留、以 $1/2$ 的概率删除，顶点始终保留。设剩余图的连通块数为 $X$ ，孤立点也算一块，求 $\mathbb E[X]$ 。若最简分数为 $a/b$ ，输出满足 $bx\equiv a\pmod{998244353}$ 的 $0\le x<998244353$ 。

输入、输出与约束 #

$1\le T\le10^3$ 。每组先输入 $3\le n\le10^5$ ，再输入 $n$ 行。第 $i$ 行先给出 $0\le c_i<n$ ，再按顺序给出它的 $c_i$ 个不同儿子，编号在 $[2,n]$ ；保证构成上述树且 $\sum c_i=n-1$ 。整个文件中 $\sum n\le3\times10^5$ 。每组输出一个模意义下的期望。

样例 #

输入 1 #

输出 1 #

374341634
694091779

样例说明 #

第一组叶子顺序为 $2,3$ ，三条边构成三角形。八种保留状态的连通块数之和为 $13$ ，所以期望是 $13/8$ ，模意义下输出 $374341634$ 。第二组叶子顺序为 $6,4,5,3$ ，增加三条链边后共八条边； $256$ 种状态的连通块总数为 $590$ ，期望 $295/128$ 。

个人代码：保留三个边界的连通性 #

一个子树与后续合并有关的顶点只有子树根、最左叶子、最右叶子。f[u][a][b][c] 统计子图保留方案数，三个布尔量分别表示“根与最左叶连通”“根与最右叶连通”“最左叶与最右叶连通”。g 对相同状态累计连通块数，而不是直接存条件期望；最终统一除以方案总数。

叶子三个边界实际是同一个点，所以只有 111 状态，f=g=1。合并第一个儿子时，枚举树边是否保留：保留则根并入儿子所在连通块，不保留则多出根这一块，代码的增量正是 1-i。

继续合并下一个儿子时，旧部分与新儿子子图的顶点互不相交。枚举树边是否保留 h，以及两片相邻叶子之间的链边是否保留 i。旧根与旧最右叶是否连通记为 b，新儿子根与其最左叶是否连通记为 d。加入两条边后，连通块减少数为

$\Delta=h+i-\mathbf1_{h=i=b=d=1}.$

只有两条边都保留且两侧原本各自连通时，第二条边才形成环、不再减少连通块。这也是不能简单使用 $n-\mathbb E[\text{保留边数}]$ 的原因。

对于旧、新状态 $s,t$ ，贡献按独立组合计数：

$f'=f_s f_t,\qquad g'=g_s f_t+f_s g_t-\Delta f_s f_t.$

新边界连通性由已有三对关系和两条新边推导，代码中的 L,R,LR 正是在枚举这些连接路径。归纳地，儿子内部情况都已由 DP 覆盖，两条外部边各枚举一次，既不漏方案也不重复。num 从 $n-2$ 开始，每遇到叶子加一，最终等于总边数 $n+k-2$ ；将根所有 g 相加并乘 $2^{-(n+k-2)}$ 得到期望。

每次合并枚举 $8\times8\times4$ 个常数状态，时间 $O(n)$ ，数组和递归栈空间 $O(n)$ 。状态虽然列了八个布尔组合，其中违反连通性传递关系的状态实际计数为零。

本地结果： 样例通过；96 棵 $3\le n\le8$ 的有序树逐一枚举全部删边方案，与该代码一致。十万点合法深链（根另挂一个叶子）在 Windows / GCC 14.2 默认链接栈设置下退出码为 0xC00000FD，即栈溢出。该环境结果不能代替 OJ 判定，但说明递归深度风险真实存在；可改为显式后序遍历来消除对默认栈大小的依赖。公开文件仍是未修改原稿。

原始 C++ 文件 #

下载 I.cpp · 验证说明

下面展示原稿，保留未完成部分和已发现问题；下载文件保留原始字节。SHA-256：bcbcdff969f415622a0aa6bfdb402b79acdab895c4278054c7519e71a9fa48d9。

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

const int N=1e5+10,mod=998244353;
int n,ans,num,f[N][2][2][2],g[N][2][2][2],tf[2][2][2],tg[2][2][2];
vector<int> vec[N];
inline void add(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline int pwr(int x,int y)
{
	int res=1;
	while(y)
	{
		if(y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return res;
}
inline void dfs(int u)
{
	for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) f[u][i][j][k]=g[u][i][j][k]=0;
	if(vec[u].empty()) ++num,f[u][1][1][1]=g[u][1][1][1]=1;
	for(auto v:vec[u])
	{
		dfs(v);
		if(v==vec[u][0])
		{
			for(int a=0;a<2;a++)
				for(int b=0;b<2;b++)
					for(int c=0;c<2;c++)
						for(int i=0;i<2;i++)
						{
							int L=(a&&i);
							int R=(b&&i);
							int LR=c;
							add(f[u][L][R][LR],f[v][a][b][c]);
							add(g[u][L][R][LR],(g[v][a][b][c]+f[v][a][b][c]*(1-i))%mod);
						}
		}
		else
		{
			memset(tf,0,sizeof tf);
			memset(tg,0,sizeof tg);
			for(int a=0;a<2;a++)
				for(int b=0;b<2;b++)
					for(int c=0;c<2;c++)
						for(int d=0;d<2;d++)
							for(int e=0;e<2;e++)
								for(int j=0;j<2;j++)
									for(int h=0;h<2;h++)
										for(int i=0;i<2;i++)
										{
											bool L=((a)||(h&&d&&i&&c));
											bool R=((h&&e)||(b&&i&&j));
											bool LR=((c&&i&&j)||(a&&h&&e));
											add(tf[L][R][LR],1ll*f[u][a][b][c]*f[v][d][e][j]%mod);
											add(tg[L][R][LR],(1ll*f[u][a][b][c]*g[v][d][e][j]+1ll*g[u][a][b][c]*f[v][d][e][j]+mod-1ll*f[u][a][b][c]*f[v][d][e][j]*(h+i-(h&&i&&b&&d))%mod)%mod);
										}
			memcpy(f[u],tf,sizeof tf);
			memcpy(g[u],tg,sizeof tg);
		}
		
	}
}
inline void solve()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int cnt;
		scanf("%d",&cnt);
		vec[i].clear();
		while(cnt--)
		{
			int x;
			scanf("%d",&x);
			vec[i].push_back(x);
		}
	}
	ans=0,num=n-2;
	dfs(1);
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
				add(ans,g[1][i][j][k]);
	ans=1ll*ans*pwr(pwr(2,num),mod-2)%mod;
	printf("%d\n",ans);
}
int main()
{
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}