思路

子树内部的平滑度和外部无关，只有根和最右元可能与其他节点作差。使用递归，暴力枚举。

为了节约时间，使用备忘。

最后只通过了#1、#2、#3-1。

代码

struct Node {
    int a;
    Node *left = nullptr, *right = nullptr;
    std::unordered_map<int, unsigned long long> buffer;
};


/*
Requires T != NULL
给定一棵子树及其先序遍历后继（右兄弟的根），求其最小平滑性。
succ < 0 表示T是最右元，没有后继。
*/
unsigned long long minD(Node *const T, const int succ = -1) {
    Node *L = T->left, *R = T->right;
    unsigned long long ans;
    auto &buffer = T->buffer;

    if (buffer.contains(succ)) {
        return buffer[succ];
    }
    if (L && R) {
        ans = std::min(
            abs(T->a - L->a) + minD(L, R->a) + minD(R, succ), 
            abs(T->a - R->a) + minD(R, L->a) + minD(L, succ)
            );
    } else if (L) {
        ans = abs(T->a - L->a) + minD(L, succ);
    } else if (R) {
        ans = abs(T->a - R->a) + minD(R, succ);
    } else {
        ans = succ > 0 ? abs(T->a - succ) : 0;
    }
    buffer.insert({succ, ans});
    return ans;
}