鬼能想到的dp定义：dp[i][j]表示在一棵i级超级树中，有j条路径同时存在且这j条路径没有公共点时，可能的情况数
刚开始我也没听懂，所以举个例子
如一个2级的超级树（没有图。。谁好心帮我画一个？）父节点为1，左右儿子为2，3
dp[2][1]=9,因为2级树里的路径一共有9条（样例），显然只有一条路径的话肯定没有公共点
dp[2][2]=9，(1,2)(1,3)(1,23)(1,32)(2,13)(2,31)(3,12)(3,21)，注意路径方向不同就是不同的
dp[2][3]=1,只有（1单独作为一条路径，2单独作为一条路径，3单独作为一条路径，共3条）这一种可能。它们没有公共点。
dp[2][4]=0,2级树只有3个点，每条路径至少1个点，所以4条路径不可能没有公共点
那么按照套路。。。递推肝它！
如果你想要得到dp[i][j]，该从什么转移过来？
情况太多了，想不出来。。。
我们尝试把dp[i][j]的情况设为已知，往后推别的
把两棵i-1级的树，配上一个根节点，合成一个i级的树，合成过程中的方案？
枚举左右子树中各有多少路径，左子树j右子树k，设sum=dp[i][j]*dp[i][k]
首先，想最简单的玩意：与根节点无关，左右子树保持原样
那么整个图中的路径数并没有变，左子树还是j个，右子树k个，只不过整个树升级了,根据乘法原理
dp[i+1][j+k]+=dp[i][j]*dp[i][k]，即dp[i+1][j+k]+=sum，就这样累加方案数就好了
下一种情况，你随便从左子树里选一条边，把这条边的终点和父节点相连，相连之后的新路径仍然与右子树当中的任何一条路径没有交点
左边的路径增长了1，但是路径的总数没有变，还是（左子树+根）有j条，右子树有k条
dp[i+1][j+k]+=sum*l; ----(2-1-1)
然后我们既然可以把终点延伸到父节点，我们也可以把起点延伸到父节点
我们还是从左子树中随便挑路径，把根节点连向它，同上，路径延长而总数不变
dp[i+1][j+k]+=sum*l; ----(2-2-1)
你现在一直是在左子树里挑边，为什么不在右子树里也挑呢？全部同理。不过是l变成了r
dp[i+1][j+k]+=sum*r; ----(2-1-2)
dp[i+1][j+k]+=sum*r; ----(2-1-2)
合并2打头的这四个式子：dp[i+1][j+k]+=2*sum*(l+r);
考虑下一种情况：左子树有j条右子树有k条，可是父节点它本身还是一条啊
那么总路径数就是（左j+右k+根1）=j+k+1
dp[i+1][j+k+1]+=sum;
再下一种情况：我们从左子树中选出一条路径，把它的终点连向父节点，在从根节点连向右子树的一条路径的起点
总路径数是j+k-1，因为你把两条合成了一条
还是举例子，若左子树有三条路径ABC，右子树3条abc。合成A和根再到a，现在的路径就是A-a, B, C, b, c，为3+3-1=5条。
而选边的方法数是j*k，这个是左连根再连右。同理还有右连根再连左，所以总数*2.
dp[i+1][j+k-1]+=sum*2*l*r;
最后一种情况，也是最恶心的：左子树一条路径终点连向父节点，再由父节点连向左子树的另一条路径的起点
证明可行性：因为dp含义中已经定义，这些路径彼此没有交点，那么从中任选两条路径后，与根节点按上述方法相连后仍然这一条路径自身没有公共点，与其他边仍然没有交点，满足条件。
dp[i+1][j+k-1]+=sum*l*(l-1) (5-1)
因为是要在l条路径中选出两条不一样的，且与顺序有关不用除2
（你可以认为是选出的第一个路径的起点作为合成路径的起点，第二条路径的终点作为合成路径的终点，那么交换这两条路径所得到的合成路径是不同的）
同理，从右边选两条：dp[i+1][j+k-1]+=sum*r*(r-1) (5-2)
合并一下：dp[i][j+k-1]+=sum*(r*(r-1)+l*(l-1));
好了，没有其他情况了。5个蓝色的式子就是全部的递推式子，不重不漏。
原文：https://www.cnblogs.com/hzoi-DeepinC/p/11208439.html