P12223 [蓝桥杯 2023 国 Java B] 非对称二叉树

题目描述

小明觉得不对称的东西有着独特的美感。 对于一棵含有 $n$ 个结点的二叉树,小明规定如果对于其中任意一个结点 $i$ 都满足条件:$\max \{h_{l_i}, h_{r_i}\} \geq k \times \min \{h_{l_i}, h_{r_i}\}$ 则此二叉树为一棵非对称二叉树。其中 $l_i, r_i$ 分别为 $i$ 的左儿子和右儿子,$h_x$ 表示以 $x$ 为根的子树的高度(如果结点 $x$ 不存在则视为高度等于 $0$)。 给定 $n, k$,计算有多少棵不同的非对称二叉树。

输入格式

输入共 $1$ 行,两个正整数 $n$、$k$。

输出格式

输出共 $1$ 行,一个整数。

说明/提示

### 样例说明 所有 $12$ 种情况如下: ![](https://cdn.luogu.com.cn/upload/image_hosting/bvh1audb.png) ### 评测用例规模与约定 - 对于 $20\%$ 的数据,保证 $n \leq 12$。 - 对于 $100\%$ 的数据,保证 $n \leq 35$,$1 \leq k \leq n$。