P14472 [集训队互测 2025] Misaka Network

由于评测机性能差异，本题时限额外增加了 3.5 秒。

一方通行在执行任务时接入了由御坂 $10032\sim 10031+n$ 号共 $n$ 位御坂妹妹组成的临时御坂网络，每位御坂妹妹拥有一些信息，为了保证存储效率，妹妹们所拥有的信息互不相同。 临时御坂网络有两种连接 $T_1,T_2$，分别构成树形结构。 由于计算需求，妹妹们有时需要交换信息。具体地，若两位御坂妹妹间同时有两种连接，那么她们可以交换她们拥有的信息（不会保留自己原有的信息），同时会交换在 $T_2$ 中的连接（即若另一位御坂妹妹和第一位有第二种连接，那么这个连接会变成她和第二位的，反之同理）。 最后之作非常好奇妹妹们拥有信息的不同状态有多少种，两种状态不同当且仅当存在一位御坂妹妹在这两种情况中所拥有的信息不同。 她设想了若干种网络的形态，并想对于每种形态都计算出上述问题的答案（因为是设想，所以并不一定保证 $n\leq 9969$）。 御坂网络在 1s 内就计算出了答案，不过因为好玩，所以最后之作想让你帮忙验算一下，你需要告诉她状态数对 $998244353$ 取模的结果。 **简要题意：** 给定两棵 $n$ 个点的无根树 $T_1,T_2$，节点编号为 $1\sim n$。 有一个 $1\sim n$ 的排列 $p$，初始时 $p_i=i$，你可以进行若干次操作，每次操作选择两个点 $u,v$，满足 $u,v$ 在 $T_1$ 中相邻且 $p_u,p_v$ 在 $T_2$ 中相邻，然后交换 $p_u$ 和 $p_v$，问能得到多少种不同的 $p$，答案对 $998244353$ 取模。 $t$ 组数据。

第一行一个整数 $t$ 表示数据组数。 接下来依次输入每组测试数据。对于每一组测试数据： 第 $1$ 行一个整数 $n$，表示临时御坂网络由 $n$ 位御坂妹妹组成。 第 $2\sim n$ 共 $n-1$ 行，每行两个整数 $u,v$ 表示 $T_1$ 中御坂 $10031+u$ 号和 $10031+v$ 号间有连接。 第 $n+1\sim 2n-1$ 共 $n-1$ 行，每行两个整数 $u,v$ 表示 $T_2$ 中御坂 $10031+u$ 号和 $10031+v$ 号间有连接。

输出共 $t$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 组数据的答案对 $998244353$ 取模的结果。

令 $\sum n$ 表示一个测试点内所有数据的 $n$ 的和。 对于所有数据，满足 $1\leq t\leq 10^5,1\leq n\leq 10^6,\sum n\leq 2\times 10^6,1\leq u,v\leq n$，保证 $T_1,T_2$ 是树。 | 子任务编号 | $n$ | $\sum n$ | 特殊限制 | 分值 | | :--: | :--: | :--: | :--: | :--: | | $1$ | $\le 10$ | $\le 100$ | 无 | $4$ | | $2$ | $\le 10^5$ | $\le 10^5$ | $T_1 = T_2$ | $4$ | | $3$ | ^ | ^ | $T_2$ 是一条链 | $12$ | | $4$ | $\le 100$ | $\le 1000$ | 无 | $8$ | | $5$ | $\le 1000$ | $\le 9969$ | ^ | $20$ | | $6$ | $\le 5 \times 10^4$ | $\le 2 \times 10^5$ | ^ | $16$ | | $7$ | $\le 2 \times 10^5$ | $\le 6 \times 10^5$ | ^ | $20$ | | $8$ | $\le 10^6$ | $\le 2 \times 10^6$ | ^ | $16$ | **建议使用较快的读入方式。**