Problem Link

题目大意

对于两棵树 $T_1,T_2$，定义 $f_i(S)$ 表示 $S$ 在 $T_i$ 上的导出子图的叶子个数。

定义 $T_1\preccurlyeq T_2$ 当且仅当 $\forall S_2\subseteq V$ 均存在 $S_2\subseteq S_1$ 使得 $f_2(S_2)\ge f_1(S_1)$。

如果 $T_1\preccurlyeq T_2$ 且 $T_2\preccurlyeq T_1$，那么认为 $T_1,T_2$ 等价。

给定 $k$ 棵树 $T_1\sim T_k$，求 $T_1\sim T_k\preccurlyeq T$ 的 $T$ 的数量，以及 $T\preccurlyeq T_1\sim T_k$ 的 $T$ 构成的等价类数量。

数据范围：$n\le 5000,k\le 1000$。

思路分析

先分析题目中给出的这个偏序关系：

用 $V_i(S)$ 表示 $S$ 在 $T_i$ 上的斯坦纳树点集，首先我们观察 $f_i(S)$ 的超集最小值，一个自然的观察是最小值在 $V_i(S)$ 取到。

证明是简单的，考虑 $V_i(S)$ 上的每个叶子，一定是 $S$ 的叶子，那么 $S$ 的每个超集一定包含这些叶子，在每个叶子以及其外面的点中至少有一个叶子，因此 $f_i(S)$ 的超集最小值就是 $f_i(V_i(S))$，记为 $g_i(S)$。

那么限制就变成 $f_2(S)\ge g_1(S)$，注意到 $g$ 有单调性，即 $S\subseteq T \implies g(S)\le g(T)$，证明就是上面的过程，$g(S)\subseteq g(T)$，而 $g(S)$ 是 $f(S)$ 的超集最小值。

那么我们把 $S$ 变成 $V_2(S)$，会减小右侧限制增大左侧限制，那么只要在 $T_2$ 上联通的 $S$ 是否有 $f_2(S)\ge g_1(S)$ 即可。

一个核心观察是，我们只要考虑 $f_2(S)=2$ 的点合法，那么就能得到 $T_1\preccurlyeq T_2$，证明如下：

首先 $f_2(S)=1$ 的点显然总是成立。

然后用数学归纳法，我们已知 $f_2(S)\le k$ 的 $S$ 都合法，现在要证明 $f_2(S)=k+1$ 的 $S$ 都合法。

不妨假设 $S'$ 是 $S$ 中选取 $k$ 个叶子生成的斯坦纳树，则 $k=f_2(S')\ge g_1(S')$。

观察 $S\setminus S'$，其形态是一条过某个叶子 $x$ 的链，取一个 $S'$ 中的叶子 $y$，则 $S=S'\cup V_2(\{x,y\})$。

记 $C=V_2(\{x,y\})$，由于 $f_2(C)=2$，因此 $g_1(C)\le f_2(C)=2$，那么 $V_1(C)$ 也是一条链。

因为 $y\in v_1(S')\cap V_1(C)$，所以 $V_1(S)=V_1(S')\cup V_1(C)$，从而 $g_1(S)\le g_1(S)+g_1(C)\le k+2$。

现在要证明 $V_1(S')$ 并上 $V_1(C)$ 的过程能删掉 $V_1(S’)$ 中的一个叶子。

这是简单的，考虑离 $x$ 最近的叶子 $z$，由于 $y\in V_1(S')$，那么 $z\in V_1(C)$，则 $z$ 在 $V_1(S)$ 中不是叶子。

所以 $g_1(S)\le k+1$，证毕。

那么 $T_1\preccurlyeq T_2$ 当且仅当 $T_2$ 中每条链在 $T_1$ 中也是一条链的子集。

我们有一种好的方法刻画这个限制，定义 $G(T)$ 为 $\{(u,v)\mid g(u,v)=2\}$，即将 $T$ 中的每个链变成一个团，此时 $T_1\preccurlyeq T_2\iff G(T_2)\subseteq G(T_1)$。

证明如下：

首先考虑充分性，建出 $G$ 的圆方树，此时 $T_1$ 上的一条链在其圆方树上也是一条链，而 $G(T_2)$ 的圆方树可以由 $G(T_1)$ 的圆方树合并若干方点得到，则其在 $T_2$ 上也是一条链。

否则考虑 $(u,v)\in G(T_2)\setminus G(T_1)$，此时 $V_2(\{u,v\})$ 在 $T_2$ 上是一条无分支的链，那么对于任意 $w$，$g_2(\{u,v,w\})=2$。

由于 $(u,v)\not\in G(T_1)$，因此 $u,v$ 路径上存在一个非二度点，取他的另一个邻居 $w$，则 $g_1(\{u,v,w\})\ge 3$。

选取点集 $V_2(\{u,v,w\})$ 即导出矛盾。证毕。

那么先解决问题二，bitset 求出 $G=\bigcap G(T_i)$，则 $G(T)\subseteq G$。

首先 $G$ 必须连通，对 $G$ 建立圆方树，容易证明每个点双连通分量都是团，那么限制就是 $G$ 每个点双连通分量在 $T$ 连通，对每个点双求生成树个数乘起来。

然后是问题一，依然求 $G=\bigcup G(T_i)$ 的圆方树，这个不用 bitset，把 $G(T_i)$ 中的团当成环，然后求圆方树即可。

现在我们有一棵圆方树，可能的操作就是合并一些相邻的方点，要求是：每个圆点度数 $\ne 2$，每个方点至多和两个非叶节点相连。

可以考虑圆方树上 dp，$f_{u,i}$ 表示 $u$ 所在的方点中有 $i$ 个非叶节点，其中 $i\in[0,2]$，具体来说：

• 如果 $u$ 是方点，那么 $i$ 表示 $u$ 所在的新方点有 $i$ 个非叶节点。
• 如果 $u$ 是圆点，那么 $i$ 表示 $fa(u)$ 所在的新方点会增加 $i$ 个非叶节点（可能把 $u$ 的儿子和 $fa(u)$ 合并）。

那么对于方点的转移，直接子树卷积即可。

对于圆点，我们分析儿子的方点会合并成什么结构，首先如果合并出一个有两个非叶节点的方点，那么 $u$ 必须是叶子，即此时 $u$ 的所有邻居都得合并。

所以我们先子树卷积算出 $\sum i=2$ 的方案。

剩下的情况，我们用 $g_{x,y}$ 表示合并出 $x$ 个没有非叶节点的方点，$y$ 个恰有一个非叶节点的方点。

然后考虑转移：

• $x+y=1$：此时儿子的方点必须和 $fa(u)$ 合并，否则 $\deg(u)=2$，转移到 $f_{u,y}$。
• $x+y=2$：此时儿子的方点不能和 $fa(u)$ 合并，转移到 $f_{u,1}$。
• $x+y>2$：可以任意选择是否有儿子和 $fa(u)$ 合并：
  • 不合并：$g_{x,y}\to f_{u,1}$。
  • 合并一个零度点：$xg_{x,y}\to f_{u,1}$。
  • 合并一个一度点：$yg_{x,y}\to f_{u,2}$。

暴力转移 $g_{x,y}$ 的复杂度是 $\mathcal O(n^3)$ 的。

注意到 $x+y\le 2$ 的转移是平凡的，我们只要维护 $\sum g_{x,y},\sum xg_{x,y},\sum yg_{x,y}$，然后对于 $x+y\le 2$ 的点重算贡献。

直接用组合计数的方法维护，$h_i$ 表示 $u$ 子树中恰有 $i$ 个儿子有一个非叶子节点。

设 $u$ 共有 $d$ 个儿子，枚举有 $j$ 个零度点和他们合并，方案数为 $h_{i}\times\binom{d-i}j\times i^j$，对于 $g_{k,i}$ 的贡献就是 $h_{i}\times\binom{d-i}j\times i^j\times\begin{Bmatrix}d-i-j\\k\end{Bmatrix}$。

因此维护答案只要预处理第二类斯特林数的行和，以及每行 $\times j$ 的和。

时间复杂度 $\mathcal O\left(nk+n^2+\dfrac{n^2k}{\omega}\right)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5005,MOD=998244353;
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
int ty,q,n;
bitset <MAXN> ch,U[MAXN],V[MAXN];
vector <int> G[MAXN],E[MAXN*2];
int st[MAXN],tp,dfn[MAXN],low[MAXN],dcnt,vc;
bool ins[MAXN];
void dfs0(int u,int fz) {
	ch.set(u),st[++tp]=u;
	if(G[u].size()==2) return dfs0(G[u][0]^G[u][1]^fz,u);
	if(fz) {
		if(ty==0) {
			for(int i=1;i<=tp;++i) V[st[i]][st[i%tp+1]]=V[st[i%tp+1]][st[i]]=1;
			tp=0;
		} else {
			while(tp) U[st[tp--]]|=ch;
			ch.reset();
		}
	}
	for(int v:G[u]) if(v^fz) ch.set(u),st[++tp]=u,dfs0(v,u);
}
void link(int u,int v) { E[u].push_back(v),E[v].push_back(u); }
void tarjan(int u,int fz) {
	dfn[u]=low[u]=++dcnt,st[++tp]=u,ins[u]=true;
	for(int v:G[u]) if(v^fz) {
		if(!dfn[v]) {
			tarjan(v,u),low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]) {
				link(++vc,u);
				while(ins[v]) link(vc,st[tp]),ins[st[tp--]]=false;
			}
		} else low[u]=min(low[u],dfn[v]);
	}
}
int C[MAXN][MAXN],pw[MAXN][MAXN];
int S[MAXN][MAXN],s1[MAXN],s2[MAXN];
ll f[MAXN*2][3],g[4][4],h[MAXN];
void dfs1(int u,int fz) {
	int m=0; f[u][0]=1;
	for(int v:E[u]) if(v^fz) {
		dfs1(v,u),++m;
		f[u][2]=(f[u][2]*f[v][0]+f[u][1]*f[v][1]+f[u][0]*f[v][2])%MOD;
		f[u][1]=(f[u][1]*f[v][0]+f[u][0]*f[v][1])%MOD,f[u][0]=f[u][0]*f[v][0]%MOD;
	}
	if(u>n||!m) return ;
	f[u][0]=f[u][1]=0;
	memset(g,0,sizeof(g)),g[0][0]=1;
	memset(h,0,sizeof(h)),h[0]=1;
	for(int v:E[u]) if(v^fz) {
		ll x=f[v][0],y=f[v][1];
		for(int i=2;i>=0;--i) for(int j=2-i;j>=0;--j) if(g[i][j]) {
			g[i+1][j]=(g[i+1][j]+g[i][j]*y)%MOD;
			g[i][j+1]=(g[i][j+1]+g[i][j]*x)%MOD;
			if(j>0) g[i+1][j-1]=(g[i+1][j-1]+g[i][j]*y%MOD*j)%MOD;
			g[i][j]=g[i][j]*x%MOD*(i+j)%MOD;
		}
		for(int i=m;i>=0;--i) if(h[i]) h[i+1]=(h[i+1]+h[i]*y)%MOD,h[i]=h[i]*x%MOD;
	}
	for(int i=0;i<=m;++i) for(int j=0;i+j<=m;++j) {
		ll z=h[i]*C[m-i][j]%MOD*pw[i][j]%MOD;
		f[u][1]=(f[u][1]+(s1[m-i-j]+s2[m-i-j])*z)%MOD;
		f[u][2]=(f[u][2]+1ll*s1[m-i-j]*i%MOD*z)%MOD;
	}
	for(int i=0;i<=2;++i) for(int j=0;i+j<=2;++j) if(g[i][j]) {
		if(i+j==1) f[u][i]=(f[u][i]+g[i][j])%MOD;
		else if(i+j==2) f[u][1]=(f[u][1]+g[i][j])%MOD;
		f[u][1]=(f[u][1]+(MOD-g[i][j])*(j+1))%MOD;
		f[u][2]=(f[u][2]+(MOD-g[i][j])*i)%MOD;
	}
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>ty>>q>>n;
	if(ty==1) for(int i=1;i<=n;++i) V[i].set();
	while(q--) {
		for(int i=1,u,v;i<n;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
		for(int i=1;i<=n;++i) if(G[i].size()!=2) { dfs0(i,0); break; }
		if(ty==1) for(int i=1;i<=n;++i) V[i]&=U[i],U[i].reset();
		for(int i=1;i<=n;++i) G[i].clear();
	}
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j&&V[i][j]) G[i].push_back(j);
	vc=n,tarjan(1,0);
	if(ty==1) {
		for(int i=1;i<=n;++i) if(!dfn[i]) return cout<<"0\n",0;
		ll ans=1;
		for(int i=n+1;i<=vc;++i) if(E[i].size()>1) ans=ans*ksm(E[i].size(),E[i].size()-2)%MOD;
		return cout<<ans<<"\n",0;
	}
	for(int i=0;i<=n;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
	for(int i=0;i<=n;++i) for(int j=pw[i][0]=1;j<=n;++j) pw[i][j]=1ll*pw[i][j-1]*i%MOD;
	for(int i=0;i<=n;++i) {
		S[i][0]=!i;
		for(int j=1;j<=i;++j) S[i][j]=(1ll*S[i-1][j]*j+S[i-1][j-1])%MOD;
		for(int j=0;j<=i;++j) s1[i]=(s1[i]+S[i][j])%MOD,s2[i]=(s2[i]+1ll*S[i][j]*j)%MOD;
	}
	for(int i=1;i<=n;++i) if(E[i].size()==1) {
		dfs1(i,0),cout<<(f[i][0]+f[i][1]+f[i][2])%MOD<<"\n";
		return 0;
	}
	return 0;
}