题目描述

小红有 $n$ 个二叉树，他准备把这些二叉树拼接起来，拼接的方式是: 选择一个二叉树 $a$ 的一个叶子，将二叉树 $b$ 的根作为该叶子的左儿子或者右儿子。这样就把 $a$ 和 $b$ 拼接起来了。

现在小红想要拼接出的二叉树的高度尽可能高，他想问你一共有多少种不同的拼接方案数。

输出描述

第一行，两个正整数 $m, n(1\leq m\leq n\leq 2\times 10^5)$ ，表示二叉树的个数和所有二叉树的结点数之和。

思路：数学

首先统计每个二叉树拥有最大高度的叶子数量。

对于每个叶子，其可以有左儿子和右儿子。

对于 $a$ 和 $b$ 两棵树，$c_a$ 表示 $a$ 拥有最大高度的叶子数量，$c_b$ 表示 $b$ 拥有最大高度的叶子数量。

如果 $a$ 在 $b$ 上面，有 $c_a\times 2$ 种选择。
如果 $b$ 在 $a$ 上面，有 $c_b\times 2$ 种选择。