自动搬运

查看原文

来自洛谷，原作者为

	lmh .

搬运于2025-08-24 23:07:12，当前版本为作者最后更新于2025-01-01 12:01:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

大概是官方题解的一些补充。

Part -1

本节中，我们将解决以下问题：

$$T_1 \preccurlyeq T_2\Leftrightarrow\ ?$$

或者说，如何将题面中的偏序关系转化为一个易于计算的等价关系？

（如果不想看数学推导的话可以直接翻到这一节末尾）

基础的观察

定义 $h(S,T)=\{v\in V|\exists u,w\in S\ \mathrm{s.t.}\ \mathrm{dist}(u,v)+\mathrm{dist}(v,w)=\mathrm{dist}(u,w)\}$（其中 $\mathrm{dist}(x,y)$ 为 $T$ 上 $x,y$ 两点之间的距离），令 $S'=h(S,T)$。

（人话：包含 $S$ 在 $T$ 上的导出子图的最小连通块）

引理：

$$min_{S\subseteq A\subseteq V}f(A,T)=f(h(S,T),T)$$

证明：

如果 $S'$ 在 $T$ 上的导出子图中存在 $0$ 度点，那么必定有 $|S'|=1$，否则这和 $S'$ 连通性矛盾。而 $\forall S\ne \varnothing, f(S,T)>0$，显然得证。

否则 $|S'|\ge 2$，对于任意一个（导出子图中的）$1$ 度点 $x\in |S'|$，必有 $x\in S$。（否则，去掉 $x$ 后 $|S'|$ 更小，且仍然满足条件）

现在令 $V'=\{v\in V|\forall u\in S',\mathrm{dist}(u,v)\ge \mathrm{dist}(x,v)\}$，或者说，$V'$ 就是 $(V-S')\cup {x}$ 的导出子图中 $x$ 所在的连通块。

对任意 $A\supseteq S$，因为 $x\in A$，所以 $A\cap V' \ne \varnothing$；令 $u$ 为 $A\cap V'$ 中 $\mathrm{dist}(x,u)$ 最大的点，那么它的度数一定不大于 $1$（否则，除了父亲之外它还需要额外连出去一个点，与距离最大的性质矛盾）

所以，$\forall A\supseteq S$，$S'$ 中任意一个度数 $\le 1$ 的点都对应至少一个 $A$ 中具有类似性质的点。

综上，得证。

（人话：把 $T$ 中 $S'$ 的导出子图删掉，再连回里面所有度数为 $1$ 的点，发现任何方案中剩下的每个连通块内至少有一个度数为 $1$ 的点，而这些连通块与 $S'$ 中的叶子一一对应）

下记 $g(S,T)=min_{S\subseteq A\subseteq V}f(A,T)=f(h(S,T),T)$。

减小枚举量

$O(2^n)$ 枚举所有 $S$ 肯定是无法接受的，我们需要更小的枚举量。

引理：

$$\forall B\supseteq A,g(A,T)\le g(B,T)$$

证明：令 $A'=h(A,T),B'=h(B,T)$，显然 $A'\subseteq B'$。

而 $h(A',T)=A'$，所以 $f(A',T)=min_{A'\subseteq X\subseteq V}f(X,T)$，所以 $f(A',T)\le f(B',T)$，得证。

$T_1 \preccurlyeq T_2\Leftrightarrow \forall S\subseteq V,g(S,T_1)\le f(S,T_2)$，考虑增大 $g$ 并减小 $f(S)$。

令 $S'=h(S,T_2)$，则显然 $g(S,T_1)\le g(S',T_1), f(S,T_2)\ge f(S',T_2)$，所以我们只需要考虑所有的联通子图。

也就是说，

$$\forall S\subseteq V\ \mathrm{s.t.}\ h(S,T_2)=S,g(S,T_1)\le f(S,T_2) \Leftrightarrow T_1 \preccurlyeq T_2) $$

引理：

$$\forall A,B\subseteq V\ \mathrm{s.t.}\ h(A,T)=A,h(B,T)=B,A\cap B\ne \varnothing, h(A\cup B,T)=A\cup B $$

证明：考虑定义，显然。

引理：

$$\forall S\subseteq V\ \mathrm{s.t.}\ h(S,T_2)=S\wedge f(S,T_2)=2,g(S,T_1)\le f(S,T_2) \Leftrightarrow T_1 \preccurlyeq T_2 $$

（也就是说，只需要考虑 $T_2$ 上所有形为链的导出子图）

证明：

必要性显然，下只考虑充分性。

对于右式中 $f(S,T_2)=1$ 的情况，显然其恒成立。

归纳证明 $f(S,T_2)=m$ 的情况。

1. $m=1,2$ 时已经成立。

2. 假设 $m\le k$ 时成立，考虑 $m=k+1$ 的情况。

任取一个 $S\subseteq V\ \mathrm{s.t.}\ h(S,T_2)=S\wedge f(S,T_2)=k+1$，设它在 $T_2$ 上导出子图中度数为 $1$ 的节点构成的集合为 $A$。

去除 $A$ 中任意元素 $x$，令 $A'=A-{x}$，$S'=h(A',T_2)$。显然 $|A|=k+1,|A'|=k$。（人话：在 $k+1$ 个叶子中选 $k$ 个叶子，找出覆盖它们的最小连通子图）

由归纳假设，$f(S',T_2)=k$。

显然 $\forall y\in A',S'\cup h(\{x,y\},T_2)=S$。（人话：把刚才那个子图拼上任意一条删去的叶子和未删去的叶子之间的链都可以得到原图）

找出 $h(S',T_1)$ 中任意一个度数为 $1$ 的节点 $z$，必定存在一个 $y\in A'$ 使得 $z$ 在 $T_2$ 中 $x$ 到 $y$ 的唯一路径上。（读者自证不难）

然后我们把 $S'$ 拼上 $h(\{x,y\},T_2)$，那么 $h(S',T_1)$ 也会拼上一条链。同时 $z\in S'\cap h(\{x,y\},T_1)$，所以拼上这条链的时候消去了一个度数为 $1$ 的点并拼上了至多两个度数为 $1$ 的点，于是 $g(S,T_1)\le k+1$。

所以，得证。

综上所述，我们只需要考虑 $T_2$ 中的链。

建图！

现在考虑一个新图 $F(T)=(V',E')(T=(V,E))$，其中 $V'=V,(u,v)\in E'$ 当且仅当 $\forall x\in h(\{u,v\},T)$，$x=u$ 或 $x=v$ 或 $x$ 在 $T$ 中的度数不超过 $2$。

也就是说，对每个中间没有分支的链，把它变成一个团再接回去。下证明 $T_1\preccurlyeq T_2$ 当且仅当 $F(T_1)$ 的边集 $E_1$ 为 $F(T_2)$ 的边集 $E_2$ 的超集。

必要性：把 $S$ 中的点放到 $F(T_1)$ 的圆方树上，容易发现这玩意所在的团在圆方树上的方点组成一条链，因而 $h(S,T_1)$ 也是一条链。

充分性：$\forall (u,v)\in E_2$，如果 $(u,v)\notin E_1$，即 $h(\{u,v\},T_1)$ 中除端点外存在度数大于 $2$ 的点，那么存在一个 $w$ 使得 $g(\{u,v,w\},T_1)=3$；但考虑到 $(u,v)\in E_2$，所以 $f(h(\{u,v,w\},T_2),T_2)=2$，矛盾。

综上，得证。

---

结论：考虑一个新图 $F(T)=(V',E')(T=(V,E))$，其中 $V'=V,(u,v)\in E'$ 当且仅当 $\forall x\in h(\{u,v\},T)$，$x=u$ 或 $x=v$ 或 $x$ 在 $T$ 中的度数不超过 $2$。也就是说，对每个中间没有分支的链，把它变成一个团再接回去。

$T_1\preccurlyeq T_2$ 当且仅当 $F(T_1)$ 的边集 $E_1$ 为 $F(T_2)$ 的边集 $E_2$ 的超集。

Part 0

本节中，我们将解决 $p=0$ 的情况。

$p=1$ 的代码难度更低，推荐先阅读它对应的章节。

由 Part -1，我们需要先求出 $k$ 个边集的并，然后对它的超集进行计数。

如果维护具体的连边关系的话可以通过 bitset 做到 $O(\frac{n^2k}{w})$，但是如果只把点双连成环，然后对新图进行 tarjan 就可以做到 $O(nk)$，理论上都可以通过，本人使用了后面一种。

然后对这玩意建圆方树，考虑树形 dp。

具体地，你可以对这棵树进行类似 compress 和 rake 的操作（或者说，合并两个有公共圆点的方点），要求操作完之后：

1. 不存在度数为 $2$ 的圆点

2. 对于每个方点，和它相连的圆点中至多 $2$ 个度数 $>1$。之后将这个数简称为方点的度数。

称合并后每个方点对应的团为一个“连通块”。

然后你用 $f_{u,i}$ 代表 $u$ 子树，根节点对应的（合并后的）方点度数为 $i$ 的方案数。

方点是简单的，直接把子树内圆点答案暴力卷积即可。

圆点就复杂很多了，要考虑如何将子树中 $0,1,2$ 度连通块合并，而且还可以把一个连通块和父亲合并。

引理：如果合并出一个度数为 $2$ 的连通块，那么必定最后只剩下这一个连通块。

证明显然，如果不满足条件的话度数必定 $+1$，这样就非法了。

所以先暴力卷积计算出 $f_{u,2}$，再考虑 $f_{u,0/1}$。

先令 $g_{x,y}$ 为 $x$ 个零度连通块，$y$ 个一度连通块的方案。

计算答案的时候需要考虑是否把一个连通块合并到上面，并注意圆点度数 $\ne 2$ 的限制。

（参见 86 分代码，建议自己手推一遍式子）

算了还是写一遍吧。假设我们目前合并了 $f_{v,0/1}$，记 $a=f_{v,0},b=f_{v,1}$，则

$$\begin{aligned} g_{x+1,y} &\leftarrow g_{x,y}\cdot a\\ g_{x,y+1} &\leftarrow g_{x,y}\cdot b\\ g_{x-1,y+1} &\leftarrow g_{x,y}\cdot bx\\ g_{x,y} &\leftarrow g_{x,y}\cdot a(x+y) \end{aligned}$$

需要注意转移顺序。

计算答案时，一个位置对答案的贡献为：

$$\begin{aligned} f_{u,0} &\leftarrow g_{1,0}\\ f_{u,1} &\leftarrow g_{x,y}\ (x\ne 1\vee y\ne 0)\\ f_{u,1} &\leftarrow g_{x,y}\cdot x\ (x+y\ge 3)\\ f_{u,2} &\leftarrow g_{x,y}\cdot y\ (x+y\ge 3) \end{aligned} $$

优化的话，考虑先确定每个子树内的方案，再进行合并。

枚举选出的一度连通块数量，它们和最终的一度连通块一一对应；对于零度连通块，枚举和一度连通块合并的个数，这部分用组合数和快速幂；剩下的可以任意合并，预处理斯特林数即可。这样单次 $O(1)$，算上前面的枚举可以做到 $O(n^2)$。

具体地，考虑如下问题：

有长度为 $n$ 的数列 $\{a_i\},\{b_i\}$，考虑如下问题：

第 $i$ 个位置有 $a_i$ 种使其值为 $0$ 的方案，$b_i$ 种使其值为 $1$ 的方案；

需要将所有位置的值确定下来，然后将其划分为若干个非空集合，使得所有集合内的数之和不超过 $1$；

假设有 $F_{x,y}$ 种将其划分为 $x$ 个和为 $0$ 的集合的方案，$y$ 个和为 $1$ 的集合的方案（两个方案不同，当且仅当任意一个位置的取值方案不同，或者所有划分集合构成的集合不同），求 $\sum_{x=0}^{n}\sum_{y=0}^{n}F_{x,y},\sum xF_{x,y},\sum yF_{x,y}$。要求 $O(n^2)$。

解法：

发现 $1$ 不能在一个集合内多次出现，所以枚举这玩意的个数。假设 $c_i$ 为所有数中恰有 $i$ 个 $1$ 的方案数，这个东西的 $O(n^2)$ 递推是容易的。

现在枚举和 $1$ 在同一组的 $0$ 的数量 $j$。选出并放这 $j$ 个数有 $\binom{n-i}{j}i^j$ 种方案，而将剩下的数划分的方案数是第二类斯特林数的前缀和。令 $S_{i,j}$ 为将 $i$ 个不同的元素划分为 $j$ 个集合的方案数，则 $S_{i,j}=S_{i-1,j-1}+jS_{i-1,j}$，预处理 $S_{i,j}$ 和 $jS_{i,j}$ 的前缀和即可。

这个东西本身是简单的，但是如果求和过程中需要处理 corner case 的话就难写了。总复杂度 $O(n^2+nk)$。

Part 1

现在考虑 $p=1$。你要对 $k$ 个图求交，bitset 可以做到 $O(\frac{n^2k}{w})$。注意实现不要让复杂度退化了，常数也最好卡一卡。

（感谢出题人提醒）实际上这里也有一个 $O(nk)$ 的做法，就是动态维护 $F(T)$ 的交的圆方树，发现两个点在同一个点双内当且仅当它们的父亲相同或者一个是另一个的祖父，点双求交就相当于分裂圆方树上的节点。

（感谢

Moeebius](https://www.luogu.com.cn/user/356003) 补充）考虑对两个圆方树求交。如果 $u$ 和 $v$ 在新图之间有边，那么它们一定在一个点双内；所以在合并前的两个圆方树上它们也一定在同一个点双内。考虑给这两个点双树钦定一个根，那么两个点在同一个点双内等价于它们的父亲相同或者一个是另一个的祖父。

考虑新图上有边的 $u$ 和 $v$，如果在原来的两个点双树上都满足它们的父亲相同，那么我们可以用哈希表记录其父亲的 pair；否则，一定存在一个是另一个的祖父，这样的点对数量是 $O(n)$ 的，可以直接枚举。具体细节可以参考下文给出的代码。

然后对于剩下的图里面的每一个点双 $|S|$（显然都是团），这里面有 $|S|^{|S|-2}$ 种方案，用快速幂直接算就做完了。图不连通时无解，记得特判。

当然还有一个小问题，考虑多个图的交，如果有一个点恰好在两个点双之内的话，会发现这时两侧的点双内选的边不能让它的度数都为 $1$（否则会多处几条跨过不同点双的边），下证明这种情况下一定无解。

假设目前的图为 $G$（不妨设其联通），与 $F(T)$ 求交之后得到 $G'$，其中 $u$ 恰好在两个点双内。

如果 $u$ 在 $F(T)$ 内连了恰一个点双，那么 $G$ 中它至少连了三个；求交之后，有部分的连接全部断掉了，图直接不连通。

否则，$u$ 在 $F(T)$ 内连了至少三个点双。

如果 $G$ 中它至少连了三个那么依然无解；考虑它只连了一个点双的情况。此时 $F(T)$ 内的边把它分成两类，也就是说至少还有一整个 $F(T)$ 上的点双与 $G$ 中的点双有交。此时，考虑它上面的任意一个点，这样 $F(T)$ 上它们相连的这条边断掉了，又由于 $G'$ 的边集是 $F(T)$ 的边集的子集，所以图直接不连通。

总复杂度 $O(n^2+nk)$，使用 bitset 则为 $O(\frac{n^2k}{w})$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5007,MOD=998244353;
ll T,n,k,ans=1,fac[N],ifac[N];
ll qpow(ll x,ll k){
	ll sum=1;
	while(k){
		if (k&1) (sum*=x)%=MOD;
		(x*=x)%=MOD;k>>=1;
	}
	return sum;
}
ll C(ll n,ll m){return (n<m||m<0)?0:fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;}
namespace A{
	ll low[N],dfn[N],timer,nV,stk[N],top,f[N<<1][3],tmp[N],sz,S[N][N],S2[N][N];
	vector<ll> to[N<<1],vec;
	bool ok[N][N];
	void dfs1(int u,int fa){
		vec.emplace_back(u);
		if (to[u].size()==2){
			dfs1(to[u][0]^to[u][1]^fa,u);return;
		}
		if (fa){
			vec.emplace_back(vec[0]);
			for (int i=1;i<vec.size();++i) ok[vec[i-1]][vec[i]]=ok[vec[i]][vec[i-1]]=1;
			vec.clear();
		}
		for (auto v:to[u]) if (v!=fa){
			vec.emplace_back(u);
			dfs1(v,u);
		}
	}
	void tarjan(int u,int fa){
		low[u]=dfn[u]=++timer;stk[++top]=u;
		int son=0;
		for (int v=1;v<=n;++v) if (ok[u][v]&&u!=v){
			if (dfn[v]) low[u]=min(low[u],dfn[v]);
			else{
				tarjan(v,u);
				low[u]=min(low[u],low[v]);son=1;
				if (low[v]>=dfn[u]){
					to[u].emplace_back(++nV);to[nV].emplace_back(u);
					while(stk[top+1]!=v){
						to[nV].emplace_back(stk[top]);to[stk[top--]].emplace_back(nV);
					}
				}
			}
		}
	}
	void dfs(int u,int fa){
		if (u<=n){
			ll t0=1,t1=0,t2=0;
			for (auto v:to[u]) if (v!=fa){
				dfs(v,u);
				t2=(t2*f[v][0]+t1*f[v][1]+t0*f[v][2])%MOD;
				t1=(t1*f[v][0]+t0*f[v][1])%MOD;
				(t0*=f[v][0])%=MOD;
			}
			f[u][2]=t2;
			tmp[0]=1;sz=0;
			for (auto v:to[u]) if (v!=fa){
				for (int i=sz;~i;--i){
					(tmp[i+1]+=tmp[i]*f[v][1])%=MOD;
					(tmp[i]*=f[v][0])%=MOD;
				}
				++sz;
			}
			if (sz==0){
				f[u][0]=1;tmp[0]=0;return;
			}
			(f[u][0]+=tmp[0])%=MOD;
			(f[u][1]+=tmp[0]*(qpow(2,sz-1)+MOD-1))%=MOD;
			if (sz>2) (f[u][1]+=tmp[0]*(S2[sz][sz]+MOD-S2[sz][2]))%=MOD;
			for (int i=sz-1,j=1;j<=sz;--i,++j) if (tmp[j]){
				for (ll t,k=0;k<=i;++k){
					t=tmp[j]*C(i,k)%MOD;
					if (j==1){
						if (k==0) (f[u][1]+=t)%=MOD;
						if (k<i) (f[u][1]+=t)%=MOD;
						if (k>1){
							(f[u][1]+=t*(S2[k][k]-S2[k][1]+MOD))%=MOD;
							(f[u][2]+=t*(S[k][k]-S[k][1]+MOD))%=MOD;
						}
					}
					else if (j==2){
						if (k==i) (f[u][1]+=t*qpow(2,i))%=MOD;
						if (k){
							(f[u][1]+=t*S2[k][k]%MOD*qpow(2,i-k))%=MOD;
							(f[u][2]+=t*S[k][k]%MOD*qpow(2,i-k+1))%=MOD;
						}
					}
					else{
						(f[u][1]+=t*S2[k][k]%MOD*qpow(j,i-k))%=MOD;
						(f[u][2]+=t*S[k][k]%MOD*qpow(j,i-k+1))%=MOD;
					}
				}
			}
			for (int i=0;i<=sz;++i) tmp[i]=0;
		}
		else{
			f[u][0]=1;
			for (auto v:to[u]) if (v!=fa){
				dfs(v,u);
				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[v][0])%=MOD;
			}
		}
	}
	void solve(){
		S[0][0]=S2[0][0]=1;
		for (int i=1;i<=n;++i) for (int j=1;j<=i;++j) S[i][j]=(S[i-1][j]*j+S[i-1][j-1])%MOD;
		for (int i=0;i<=n;++i) for (int j=1;j<=n;++j) S2[i][j]=(S[i][j]*(j+1)+S2[i][j-1])%MOD;
		for (int i=0;i<=n;++i) for (int j=1;j<=n;++j) (S[i][j]+=S[i][j-1])%=MOD;
		nV=n;
		while(k--){
			for (int i=1,u,v;i<n;++i){
				cin>>u>>v;to[u].emplace_back(v);to[v].emplace_back(u);
			}
			for (int i=1;i<=n;++i) if (to[i].size()!=2){dfs1(i,0);break;}
			for (int i=1;i<=n;++i) to[i].clear();
		}
		tarjan(1,0);
		for (int i=1;i<=n;++i) if (to[i].size()==1){
			dfs(i,0);
			cout<<(f[i][0]+f[i][1]+f[i][2])%MOD<<endl;
			return;
		}
	}
}
namespace B{
	struct TREE{
		ll p[N<<1],nV;
		vector<ll> to[N<<1];
		void clear(){
			for (int i=1;i<=nV;++i) to[i].clear();
		}
	}T1,T2;
	void dfs(TREE& T,int u,int fa){
		T.p[u]=fa;
		for (auto v:T.to[u]) if (v!=fa) dfs(T,v,u);
	}
	ll low[N],dfn[N],timer,nbcc,stk[N],top,nV,ok[N];
	vector<ll> to[N],bcc[N],vec[N<<1];
	unordered_map<ll,int> mp;
	ll Hash(ll x,ll y){return (x<<16)|y;}
	void insert(ll p,int x){
		if (mp.find(p)==mp.end()) mp[p]=++nV;
		vec[mp[p]].emplace_back(x);
	}
	void merge(TREE& T1,TREE& T2){
//		cout<<"merge"<<endl;
		for (int i=2;i<=n;++i) insert(Hash(T1.p[i],T2.p[i]),i);
		for (int j,i=2;i<=n;++i) if (j=T1.p[T1.p[i]]){
			if (T2.p[i]==T2.p[j]) insert(Hash(T1.p[i],T2.p[i]),j);
			else if (T2.p[T2.p[i]]==j) insert(Hash(T1.p[i],T2.p[i]),j);
			else if (T2.p[T2.p[j]]==i){
				insert(Hash(T1.p[i],T2.p[j]),i);
				insert(Hash(T1.p[i],T2.p[j]),j);
			}
		}
		for (int j,i=2;i<=n;++i) if (j=T2.p[T2.p[i]]){
			if (T1.p[i]==T1.p[j]) insert(Hash(T1.p[i],T2.p[i]),j);
			else if (T1.p[T1.p[i]]==j) insert(Hash(T1.p[i],T2.p[i]),j);
			else if (T1.p[T1.p[j]]==i){
				insert(Hash(T1.p[j],T2.p[i]),i);
				insert(Hash(T1.p[j],T2.p[i]),j);
			}
		}
		T1.clear();T1.nV=n+nV;
		for (int x=1;x<=nV;++x){
			for (auto u:vec[x]) if (!ok[u]){
				ok[u]=1;
				T1.to[u].emplace_back(n+x);T1.to[n+x].emplace_back(u);
			}
			for (auto u:vec[x]) ok[u]=0;
		}
		dfs(T1,1,0);
		for (int i=1;i<=nV;++i) vec[i].clear();nV=0;mp.clear();
	}
	void build(TREE& T,int u,int fa,int now){
//		cout<<u<<' '<<fa<<' '<<now<<endl;
		if (fa){
			T.to[now].emplace_back(u);T.to[u].emplace_back(now);
			if (to[u].size()==2){build(T,to[u][0]^to[u][1]^fa,u,now);return;}
		}
		for (auto v:to[u]) if (v!=fa){
			++T.nV;
			T.to[T.nV].emplace_back(u);T.to[u].emplace_back(T.nV);
			build(T,v,u,T.nV);
		}
	}
	void build(TREE& T){
//		cout<<"build"<<endl;
		for (int u,v,i=1;i<n;++i){
			cin>>u>>v;to[u].emplace_back(v);to[v].emplace_back(u);
		}
		T.nV=n;
		for (int i=1;i<=n;++i) if (to[i].size()!=2){build(T,i,0,n);break;}
		dfs(T,1,0);
		for (int i=1;i<=n;++i) to[i].clear();
	}
	void convert(const TREE& T){
		for (int _=n+1;_<=T.nV;++_){
			auto& vec=T.to[_];
//			cout<<_-n<<endl;
//			for (auto u:vec) cout<<u<<' ';cout<<endl;
			for (auto u:vec) for (auto v:vec) if (u!=v) to[u].emplace_back(v);
		}
	}
	void tarjan(int u,int fa){
		low[u]=dfn[u]=++timer;stk[++top]=u;
		int son=0;
		for (auto v:to[u]) if (u!=v){
			if (dfn[v]) low[u]=min(low[u],dfn[v]);
			else{
				tarjan(v,u);
				low[u]=min(low[u],low[v]);son=1;
				if (low[v]>=dfn[u]){
					bcc[++nbcc].push_back(u);
					while(stk[top+1]!=v) bcc[nbcc].push_back(stk[top--]);
				}
			}
		}
		if ((!fa)&&(!son)) bcc[++nbcc].push_back(u);
	}
	void solve(){
		build(T1);
		while(--k){
			build(T2);
			merge(T1,T2);
			T2.clear();
		}
		convert(T1);
		tarjan(1,0);
		for (int i=1;i<=n;++i) if (!dfn[i]){
			cout<<0<<endl;return;
		}
		for (int i=1;i<=nbcc;++i) (ans*=qpow(bcc[i].size(),bcc[i].size()-2))%=MOD;
		cout<<ans<<endl;
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	for (int i=fac[0]=1;i<N;++i) fac[i]=fac[i-1]*i%MOD;
	ifac[N-1]=qpow(fac[N-1],MOD-2);
	for (int i=N-1;i;--i) ifac[i-1]=ifac[i]*i%MOD;
	cin>>T>>k>>n;
	if (T==0) A::solve();
	else B::solve();
	return 0;
}