注意类似题目这种建树的方式，建出来可能是树，也可能是堆，而前者不一定是连续的编号，后者一定是连续的编号，这就导致了后者左右子树中一个是完全二叉树，另一个不是完全二叉树（这里就要利用这个性质优化时间复杂度）；自己做的时候就是没有抓住这个性质导致没有做出来
显然考虑贡献，设\(s_{i,j}=x\)，我们挑出两个点作为路径的起点和终点，然后算这条路径的\(s=x\)的数量，但是发现算不出来，因为缺少长度，所以我们引入长度，假设这个路径的长度为\(y\)，那么方案数显然就是\(x^y-(x-1)^y\)；而除了这条路径的其余\(n-y\)个点，染色方案数为\(m^{n-y}\)；假设整棵树长度为\(y\)的路径有\(k_y\)个，那么\(x\)对答案的贡献就是
\[\overset{\text{MAXL}}{\underset{y=1}{\sum}}m^{n-y}(x^y-(x-1)^y)k_yx \]（其中\(\text{MAXL}\)为最长路径，这个需要分类讨论），所以答案就为
\[\overset{m}{\underset{x=1}{\sum}}\overset{\text{MAXL}}{\underset{y=1}{\sum}}m^{n-y}(x^y-(x-1)^y)k_yx \]，考虑到\(k_y\)与\(x\)无关且\(\text{MAXL}\)很小，所以交换美剧顺序，有
\[\overset{\text{MAXL}}{\underset{y=1}{\sum}}k_y\overset{m}{\underset{x=1}{\sum}}m^{n-y}(x^y-(x-1)^y)x \]所以现在的当务之急是计算\(k_y\)。unordered_map好像不能使用pair，所以我们用数组来DP（而不是用unordered_map）
设\(g[i][j]\)表示从根节点往下走了\(i\)层（每一层走的方向是确定的，我们都会向非完全二叉树的方向走；当然有时两个子树都是非完全二叉树，比如\(n=11\)，此时我们向右走），以当前节点为子树，长度为\(j\)的总方案数；\(h[i]\)表示从根节点往下走了\(i\)层，以当前节点为子树，这棵子树的深度（从\(0\)开始计数）
计算\(g[i][j]\)的时候，我们已经计算好了\(g[i+1]\)，所以\(g[i][j]+=g[i+1][j]\)；\(g[i][j]\)还要加上完全二叉树的这棵子树的贡献，这个比较容易计算，设\(G[i][j]\)表示深度为\(i\)的完全二叉树，长度为\(j\)的总路径数，推导见代码，于是\(g[i][j]+=G[h[i]-1][j]\)（假设右子树是非完全二叉树，左子树是非完全二叉树的情况有一点点小的改变，但是道理一样）；接下来只需要计算经过经过当前根节点的路径就好了，这样的路径又分为两类，一类是根节点为端点，另一类是根节点为中转点。对于前者非常好计算，后者需要枚举一颗子树的长度（为了方便枚举非完全二叉树的长度）然后计算出另一颗子树的长度
时间复杂度为\(O(\sum m\log n+T\log^3 n)\)
标签：sum,路径,节点,Plan,overset,长度,Travel,二叉树 From： https://www.cnblogs.com/dingxingdi/p/18357824