solution
旅行规划
从最⼩的边开始，假设最⼩的边删去后可以把树分成 T1 和 T2 两个⼦树，那么我们只
要保证先访问 T1 中的所有点再访问 T2 中的点，就可以保证最⼩边恰好被经过⼀次。
那么我们对 T1 T2 重复上述步骤，就可以得到⼀个总代价为所有边权和的⽅案，注意
到所有边权的和是理论的最⼤值，⽽以上部分能够证明这个最⼤值可以取到，那么答
案就是边权和。
括号
注意到 \(a - (b - (c - (d\cdots = a - (b - c) - (d\cdots)\), 因此括号层数不超过 \(2\). 记 \(f(i, 0/1/2)\) 表示考虑前 \(i\) 个数, 当前有几层括号能得到的最大值, 讨论一个位置放不放括号转移即可. 时间复杂度 \(O(n)\).
杨辉三角
观察杨辉三角形可以知道，从左至中间都是递增的，同时又根据对称性，把所有大于每行中点的点对称到左边来。
这样从目标点出发，每次都往左上方走，然后，走到第0列的时候就往上一直走（全为1），即最小值。
结果可以表示为\(C(n,k)+C(n-1,k-1)+……+C(n-k+1,1)+C(n-k,0)+C(n-k-1,0)+……C(0,0)\)
然后把\(C(n-k,0)\)写成\(C(n-k+1,0)\)
这样，上面式子右边那一段，可以从尾到头依次合并，最终合并为\(C(n+1,k)\)
如果都用Lucas定理求组合数会T
可以开一个数组，把所有小于\(10000\)的数的阶乘对所有小于\(10000\)的素数的取模预处理出来（这里要注意阶乘所含有的素数因子要拿出来单独处理）
蘑菇
\(16\)分做法
枚举哪条边被分解了
32 分做法
设 \(dp[i][j]\)代表以$ i \(为根的子树中，\) i \(所在连通块大小为\) j $时的答案。暴力合并转移复杂度 \(n^3\)
48 分做法
与 32 做法相似，但是在转移的过程中$ j \(只枚举\) 1 \(到以\) i \(为根的子树大小。 这时候我们发现合并转移时每个点对在它们的\) LCA \(处造成一次运算。复杂度\) n^2$。
72 分做法
我觉得肯定有这样的做法， NTT 啊什么的。但我不会。
100 分做法
考虑联通块之积的组合意义。相当于把树划分成几个连通块，每个连通块里选一个点的方案数。那么，记$ g[i]\(代表以\) i \(为根，\) i \(所在连通块还没有被选择的点的方案数，\) f[i]\(代表以\) i \(为根，\) i \(所在的连通块已经选了一个点的方案数。 复杂度\) O(n) $