如果这是我最后一篇题解，请每年为我上坟。

Galgame

题目传送门

Decription

as_lky 搞到了很多 Galgame（真的很多！）。一款 Galgame 可以被描述为很多场景（Scene）的结合，它们形成了一棵 以 1 为根 的二叉树，每一个结点都是一个场景，一个结点的左儿子和右儿子分别对应在该场景选 A 选项和 B 选项能够到达的场景（可能会到达空场景，即游戏结束），我们称其为 A 场景和 B 场景。

as_lky 如下定义了两个不同的 Galgame 场景哪个更有趣（两款 Galgame 谁更为有趣也就取决于它们的初始场景谁更有趣）：

1. 如果这两个场景能够到达的场景总数（即通过任意选择能够到达的不同场景总数，包括该场景本身）不一样，那么能到达的场景数更多的那个更有趣；
2. 如果这两个场景的 A 场景不一样有趣，那么 A 场景更有趣的场景更有趣；
3. 否则这两个场景谁更有趣完全等价于他们 B 场景谁更有趣。

值得注意的是，空场景能到达的场景数被定义为 0。

例如，对于上图给出的例子，我们这样判定 1 和 7 这两个场景谁更有趣：

• 首先，1 和 7 能到达的场景数都是 6，因此我们首先尝试比较其 A 场景：2 和 8。
• 由于 2 和 8 能到达的场景数不同（分别是 3 和 2），则 2 场景比 8 场景更有趣；继而可以得到 1 场景比 7 场景更有趣。

as_lky 定义两个 Galgame 场景本质相同，当且仅当这两个场景都为空场景，或者它们的 A 场景本质相同且 B 场景本质相同。

as_lky 认为一款 Galgame 的有趣度是所有可能的、本质不同的、不及这款 Galgame 有趣的 Galgame 数量。现在 as_lky 给了你一款 Galgame，请告诉他这款 Galgame 的有趣度是多少。as_lky 觉得这个数字可能有些大，所以他想让你输出这个数字对 \(998244353\) 取模的结果。

Solution

不难看出，我们可以设 \(f(x)\) 表示以 \(u\) 为根的子树，子树大小相同但不比该子树有趣的个数。可以得到转移式：

\[f(x)=f(lson(x))\times H(siz(rson(x)))+f(rson(x))+\sum_{i=0}^{siz(lson(x))-1} H(i)\times H(siz(x)-i-1) \]

其中 \(H(x)\) 表示 Catalan 的第 \(x\) 项。

然后我就只会 \(\Theta(n^2)\) 了。。。

---

我们可以考虑启发式合并，\(siz(lson(x))\le siz(rson(x))\) 的时候直接暴力计算即可。

考虑 \(siz(lson(x))>siz(rson(x))\) 的情况，我们可以总方案减去不合法方案，即：

\[H(siz(x))-\sum_{i=siz(lson(x))}^{siz(x)-1}H(i)\times H(siz(x)-i-1) \]

时间复杂度 \(\Theta(n\log n)\)。

最后答案显然就是：

\[f(1)+\sum_{i=1}^{n-1} H(i) \]

Code

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

#define Int register int
#define mod 998244353
#define MAXN 1000005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,H[MAXN],siz[MAXN],fac[MAXN << 1],son[MAXN][2],ifac[MAXN];

int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
int qkpow (int a,int b){int res = 1;for (;b;b >>= 1,a = mul (a,a)) if (b & 1) res = mul (res,a);return res;}

int Solve (int x){
	if (!x) return 0;
	int ret = add (mul (Solve (son[x][0]),H[siz[son[x][1]]]),Solve (son[x][1]));
	siz[x] = siz[son[x][0]] + siz[son[x][1]] + 1;
	if (siz[son[x][0]] <= siz[son[x][1]])
 		for (Int i = 0;i < siz[son[x][0]];++ i)
			ret = add (ret,mul (H[i],H[siz[x] - i - 1]));
	else{
		ret = add (ret,H[siz[x]]);
		for (Int i = siz[son[x][0]];i < siz[x];++ i)
			ret = dec (ret,mul (H[i],H[siz[x] - i - 1]));
	}
	return ret;
}

signed main(){
	read (n);
	for (Int i = 1;i <= n;++ i) read (son[i][0],son[i][1]);
	fac[0] = 1;for (Int i = 1;i <= n << 1;++ i) fac[i] = mul (fac[i - 1],i);
	ifac[n + 1] = qkpow (fac[n + 1],mod - 2);for (Int i = n + 1;i;-- i) ifac[i - 1] = mul (ifac[i],i);
	for (Int i = 0;i <= n;++ i) H[i] = mul (fac[i << 1],mul (ifac[i],ifac[i + 1]));
	int ret = Solve (1);for (Int i = 1;i < n;++ i) ret = add (ret,H[i]);
	write (ret),putchar ('\n');
 	return 0;
}