题意

给出n,m,有一颗二叉树，两个子树之间的差不超过m，二叉树的总高度为n，然后求这颗树中左右子树之间的最大差值。

解析

要求最大的差值，必定就是一颗子树上的节点尽可能地多，另一个尽可能的少，尽可能多的很容易就能解决，就是挂满就完事了，即 $2^{n-1}-1$,现在就是解决另一颗子树如何做到最少，这里我们可以通过递推，假设m为2，假设我们已经知道了$dp[1],dp[2]$现在求解$dp[3]$

那么因为我们要求就是在的基础上再向上加一个节点，这个就是那个加一，然后我们再挂一颗子树在另一边，这另一颗子树自然是尽可能地小，最大的差值就是m,所以挂在另一边的就是

因此我们可以得出递推式

但是我们还要小心

所以最后的结果为

代码

#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#define ll long long
using namespace std;
const int N = 1e5 + 7;
ll dp[100];
int main(void) {
    int n,m;
    cin>>n>>m;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i)
        dp[i] = dp[i - 1] + dp[max(i - m - 1, 0)] + 1;
    ll ans = 1ll<< n - 1;
    ans -= dp[n - m - 1];
    cout << ans - 1 << endl;
    return 0;
}