B
对于一个子串，它一定会是两条出边，当且仅当其所有字符相同时达到的节点相同（不妨设这样的字符串为”特殊串“）。
如果不考虑特殊串，答案就是 \(2^n - 1\)。
而只要到达了特殊串，后面就只有 \(|s|\) 种路径了，所以只用在第一次到达特殊串时减去对应的方案数即可。
设特殊串对应 \(s_{l\sim r}\)，那么需满足 \(s_l \ne s_{l - 1} 或 s_r \ne s_{r + 1}\)，就只有 \(O(n)\) 种。所以枚举第一个到达的特殊串，用组合数算算到达它的方案数，再减去它往后的方案数。
时间复杂度：\(O(n)\)
还是有点意思吧，最开始脑瘫的把特殊串的定义搞错了，以为是 \(s_l = s_r\) 就做不了。
抓住到达特殊串后方案数可以轻松算出这个特点，只需要关注第一次到达的特殊串即可。
D
\(n \le 26\)
有一个十分暴力的 \(O(3^n)\) 暴搜做法（枚举每个蛋糕分给谁。）
以为是个剪枝题，赛时首先钦定了 \(2\) 个蛋糕，然后暴搜时加了一堆最优性剪枝，大样例跑的飞起，结果只过了 \(n \le 20\)。
\(3^n\) 很大，但是 \(3^{\frac{n}{2}}\) 还好，考虑折半搜索。
假设左边三个人得到的蛋糕 \(a_l, b_l, c_l\)，右边是 \(a_r, b_r, c_r\)。不妨设 \(a \le b \le c\)，即 \(a_l + a_r \le b_l + b_r \le c_l + c_r\)，权值为 \((c_l + c_r) - (a_l + a_r)\)。把关于 \(l, r\) 的分开，移项可得：
是个标志的二维数点问题，就做完了。
时间复杂度 \(O(m \log m)(m = 3^{\frac{n}{2}})\)。
没怎么想折半，以为要优化成 \(2^n\) 之类的复杂度或者就是要剪枝（大样例太水了）。