CF1868C
首先想拆开每条路径的贡献。
对于一条路径，长度为 \(len\) 枚举最大值为 \(x\)，那么贡献是 \(x\times(x^{len}-(x-1)^{len})\times m^{n-len}\)。
其中 \(x^{len}-(x-1)^{len}\)，表示最大值小于等于 \(x\) 的方案数容斥掉最大值小于等于 \(x-1\) 的方案数。
如果我们知道所有长度为 \(len\) 的路径个数 \(Ans_{len}\)，那么就可以通过枚举最大值的方式来计算贡献。
现在只需求出 \(Ans\)，其中定义域大小为 \(O(\log n)\)。
在转移的时候，只需要记录 \(f_i,g_i\) 分别表示当前长度为 \(i\) 的路径条数；长度 \(i\) 到根的路径条数。
\(f_i=f_{ls,i}+f_{rs,i}+g_i+\sum_{j+k+1=i} g_{ls,j}\cdot g_{rs,k}\)
看似状态数为 \(O(n)\)，但是一个完全二叉树左右儿子至少有一个是满二叉树，所以实则只有 \(O(\log n)\)。
然后便做完了。