题解
为了方便说明，先定义几个函数和变量：
- $len(i,j)$表示从$i$到$j$整个路径上所经过的节点数。比如样例1中，$len(2,3)=3$, $len(1,2)=1$。
- $max\_deep$，表示整棵树的高度。比如$n=2$时，$max\_deep=2$。$n=9$时，$max\_deep=4$。
- $deep(node)$表示计算某个节点的深度。
- $number\_of\_nodes\_at\_layer(layer)$在这棵树里的某一层有多少节点。比如$n=4$时，$number\_of\_nodes\_at\_layer(2)=2$, $number\_of\_nodes\_at\_layer(3)=1$
整体思路
总共分三步。
第一步，维护一个$dp\_s[i][j]$，用来表示长度为$j$的一条路径，其$s$的值（也就是路径上最大的$a$）为$i$的所有可能性。其中$1\leq i\leq m$，$1\leq j \leq 2 \cdot max\_deep - 1$。
（也就是说，这个树上，可能的最长的路径最多包含$2 \cdot max\_deep - 1$个点）
第二步，维护一个$dp\_len[i]$，用来表示在这棵树上，长度为$i$的路径共有多少条。比如$n=4$，$dp\_len[2]=3$，$dp\_len[1]=4$。
第三步，计算最终结果。最终结果等于$\sum_{len=1}^{2 \cdot max\_deep - 1}dp\_len[len]\cdot m^{n-len} \cdot (\sum_{s=1}^{m} s\cdot dp\_s[s][len])$。
意思是对于每一个指定的长度的路径：$len$。
这种路径一共有$dp\_len[i]$种。
对于这条路径之外的点，可以任意选择，所以有$m^{n-len}$种选择。
对于这条路径之内的点，对于每一个可能的$s$，有$dp\_s[s][len]$种选择方法。且最后计算结果的时候需要乘以$s$。
怎么想到的
主要是两个点：
- 一个是$\sum_{i=1}^n\sum_{j=i}^n s_{i,j}$毕竟是求和，且最后需要的结果也是对这个求和的再次求和。那么很自然的回想试试把$s_{i,j}$交换出来。统一求和。
- 因为$dp\_s[i][j]$太容易得到了。同时一旦有了$dp\_s[i][j]$，距离结果差的就是$dp\_len[i]$。而$dp\_len[i]$看上去像是一个非常经典的问题，目测一定是有解决方案的。
$dp\_s[i][j]$的计算
首先，不难想到一个朴素的排列组合的方法。显然$dp\_s[i][j]=\sum_{k=1}^{j} C_j^k\cdot (i-1)^{j-k}$。
也就是说从$j$个节点里选出$k$个，使得其点权为$i$，其余的点的点权在$1$到$i-1$之间任意选择。
但是这个做法有个问题，其时间复杂度为$O(m\cdot max\_deep^2)\approx 10^5 \cdot {(10^2)}^2 \approx 10^9$。毕竟对于每一个$i,j$都需要循环计算$k$。
于是我们尝试观察$dp\_s[i][j]$于其他节点之间的关系。不难发现$dp\_s[i][j]=i\cdot dp\_s[i][j-1] + \sum_{k=1}^{i-1} dp\_s[k][j-1]$。
也就是说，要么前面$j-1$个点的最大值已经是$i$了，那么新的点可以在$1$到$i$之间任意选择。
否则，那么前面的最大值可以是任何小于$i$的值，但新的点必须是$i$。
而这里的$\sum_{k=1}^i dp\_s[k][j-1]$可以用一个前缀和来维护。所以复杂度是$O(m\cdot max\_deep)$。
$dp\_len[i]$的计算
这个我估计有很多做法，我这里采用了一个比较朴素的解法。
对于一条路径来说，只需要知道它的起点和终点，我们就能知道这条边的长度以及其经过的所有点。
进一步加入我们知道一条路径的起点，和这条路径最顶层的点，且再知道这条路径的终点的深度。那么我们就能知道：1. 这条路径的长度；2. 这样的路径的所有可能数。
记起点的为$from$，最顶层的点的深度为$father$，终点的深度为$to$。那么不难发现，对于每一组$[from, father, to]$可知其长度为$[father-deep(from)] + (father - to) + 1$，且共有$2^{to - father -1}$种可能。
所以$dp\_len[father-deep(from) + (father - to) + 1]+=number\_of\_nodes\_at\_layer(deep(from))\cdot 2^{to - father -1}$。也就是枚举$deep(from)$，对于每一个深度为$deep(from)$的起点，再枚举路径最顶层点的深度，再枚举终点的深度，依次累加到$dp\_len[i]$中。
（注意，此处是选择了一个固定的起点。不是选择起点的深度。也就是起点固定，终点不固定）
这里有两个漏洞：
1. 当$father=to$时，其实也是只有1种可能。特殊处理就好。
2. 当$deep(from)=to$的时候，显然很多路径被算了两次。这个比较麻烦。
对于第二个漏洞，我选择换个做法单独处理。
所以首先，上面的计算过程中，对于$to$的枚举，限定其范围只到$deep(from)-1$。也就是终点的深度永远比起点小。这样无论如何，至少起终点深度不同的情况下，我们的结果是正确的。而且也包含了对不完全二叉树的处理。
对于起终点的深度相同，我们直接考虑其最顶端的点的情况。因为两个叶子节点必然分别在最顶端节点的左右两棵子树中。
自然的，由于非完全二叉树的缘故，这样的左右子树有三种不同的情况：1. 子树是完全的；2. 子树是不完全的；3. 子树深度不够，在要求的深度没有节点了。
记起终点的深度为$target$，最顶端的点的深度为$father$。
那么对于第一种情况，对于每一个$father$，有$(2^{target-father -1})^2$种选择。且第一种情况共有$\lfloor\frac {number\_of\_nodes\_at\_layer(target)} {2^{target-father}}\rfloor$个father满足条件。
对于第三种，显然有0种可能。
对于第二种，显然只会有一个father符合第二种的条件。对于其选择数，我们需要计算其右子树有多少个节点。不难发现其右子树有$\max([number\_of\_nodes\_at\_layer(target) \% (2^{target-father})] - (2^{target-father -1}),0)$个叶子节点，记为$num\_right$（也就是减去左子树，减去第一种情况，剩下的）。所以其选择数为$num\_right \cdot (2^{target-father -1})$。
最后把上面的结果全部加到$dp\_len[i]$里即可。也就是$dp\_len[(target-father) * 2 + 1]+=(2^{target-father -1})^2\cdot \lfloor\frac {number\_of\_nodes\_at\_layer(target)} {2^{target-father}}\rfloor +$$(2^{target-father -1}) \cdot \max([number\_of\_nodes\_at\_layer(target) \% (2^{target-father})] - (2^{target-father -1}),0) $
代码
Java
C++