翻车+翻船，再次被爆踩
现在我只好走路了
没开longlong见祖宗。
（而且我数组差点只开了10^5。。。。。。）
讲题时可能也许出了点锅。。。
强调一下，O(n^6)判掉那些方案数为0的东西就可以过了。
首先我们转移，可以由一个子树或两个子树转移过来。
对于一个子树（为\(f[i][j][k]\)），我们只需要加上方案数乘以\((i+1)\)（因为当前节点可以为\(1\)~\(i+1\)中的任意一个）
对于两个子树（另一个为\(f[i1][j1][k1]\)），我们转移的时候要乘以\(C(i,i+i1)\)因为我们可以把编号任意取出i个给大小为i的子树，然后还要乘以\((i+1)\)理由在上面。
有种特殊情况，就是两个子树大小都是一样的，那我们就要将方案数乘后再除以\(2\)。
大概就是这样子的了。
我们可以优化，用数学归纳法得知，最大匹配的差的绝对值小于等于\(1\)。
所以在枚举\(k\)和\(k1\)的时候，我们就可以枚举差值，就可以少了\(O(n^2)\)
我们可以按照输入顺序来建一棵树。
然后对于那些不在树上的边（一定会形成环），就搞一搞节点个数并用并查集来合并+维护。
其实很容易理解的。
这次的时间分配好像还是不合理。
然后对于树上的题还是没有想得太深刻。
没有在晚上前改完题。\(GG\)
原文：https://www.cnblogs.com/jz929/p/12208747.html