小宝是一个爱 Froggy 的男孩子， 活点地图上显示，在 Hogwarts 的黑湖上，有 nnn 个石墩，编号为 111 到 nnn，第 iii 个石墩上有 aia_iai 只青蛙， 小宝想进行 qqq 次独立的操作，每次只保留编号在 [l,r][l,r][l,r] 中的石墩， 小宝想起了麻瓜的 OI，想起了二叉树，他决定将这些石墩用一些边连起来，并指定一个根，使之成为一棵
小宝是一个爱 Froggy 的男孩子。 活点地图上显示，在 Hogwarts 的黑湖上，有 nnn 个石墩，编号为 111 到 nnn，第 iii 个石墩上有 aia_iai 只青蛙。 小宝想进行 qqq 次独立的操作，每次只保留编号在 [l,r][l,r][l,r] 中的石墩。 小宝想起了麻瓜的 OI，想起了二叉树。他决定将这些石墩用一些边连起来，并指定一个根，使之成为一棵二叉树。 二叉树虽然是麻瓜发明的，但是小宝觉得二叉树的中序遍历充满魔力，于是他希望对这棵二叉树中序遍历得到的编号序列恰好为 l,l+1,…,rl, l+1, ldots, rl,l+1,…,r。 小宝今天又从全年级第一的麻瓜出身的 Hermione 那学了一种新的数据结构——堆。他希望借这棵二叉树复习一下堆的结构，所以他又规定这棵二叉树需要满足任意一个不为根的石墩的青蛙数量不少于这个石墩的父亲的青蛙数量。 对于每次操作，请你帮助小宝求出有多少种符合条件的不同的二叉树。 两棵二叉树不同当且仅当满足下列条件之一： 根的编号不同； 存在两个石墩 u,vu,vu,v 满足恰好在其中一棵树中存在边 (u,v)(u,v)(u,v)。 由于答案可能很大，你只需要输出答案对 998 244 353998,244,353998244353 取模的结果即可。
（图片来源网络，侵删）
标签： HBC208210青蛙树题解
