思路比较简单但是很经典的一题，最近一直在补数学。。
用dp(u)表示以节点u为根的种类数，则由基本的组合数学可以得出\[dp(u)=(\frac{(n-1)!}{\prod size(v)})*\prod dp(v),\ u\ is\ v’s\ parent\] 其中\[size(v)\]是以v为根的子树的大小。然后由于这里模值是任取的，所以不能用求逆元的方式来做，否则的话也太简单了。
考虑进一步化简这个式子，把\[dp(v)\] 们展开（脑海中展开）可以发现对于每个节点来说，他以 \[(size(v)-1)!\]的形式出现在分子上一次，以\[size(v)!\]的形式出现在分母上一次，所以最终把所有节点（不仅仅是root的直接儿子）全部代进去就可以得到\[dp(root)=(\frac{(n-1)!}{\prod_{v=2}^{v=n} size(v)})\]
继续阅读“[组合数学][大组合数取模][TreeDp] UVA 1436 Counting heaps”
这个题确实是，自己想没有整出来。由于多考虑了一层，状态变得复杂了。
首先还是转化为有根树去做，然后考虑下自底向上的推法。因为这里多考虑一层，所以还需要考虑子节点的放置情况，也就是除了考虑i节点放A/放B/不放，还需要考虑i的子节点，有没有放B/放A/不放，这样的话可以发现所有的情况到最后可以归类为4类，1）i处放B 2）i处放A且子节点放A/放B/没但是其字节点全放A/B，或者i处不放，其字节点至少有一个放B 3）i处不放，但是子节点全为2状态 4）能保证父节点放一个B就能覆盖到往下所有未覆盖路径的任意状态。然后就可以把状态转移方程搞出来，记忆化搜索即可。
自己思考存在的问题：脱离了无后效性这个基本点在想。如果按照一遍dfs来dp的思路，应该是保证了子树推出来之后才能推更高的祖先。
wa的话，因为用了一个cur的变量，之后再用却没有正确赋值。。。
自己思路的问题：每次用一个中转节点多连一条线就是等于跳过了一个节点，想到了偶数就是/2，奇数是+1/2，但是没有想到怎么去统计实现。
这个问题最后的答案可以表示为（S+O)/2，其中S是所有点对之间的路径长度之和，O是路径长度为奇数的路径的数量。然后就是如何计算这两个数字的问题。
我以前的理解是求S得用两遍dfs的treeDP，然而这次学到了新操作就是可以分别考察每一条边他被多少对点之间的路径包含了，只需要求出有根树每个点对应的子树中的节点个数即可，S+=(n-subts[x])*subs[x]。
求O的方法就更妙了，画出来一颗有根树就可以发现，两个节点之间的距离奇偶性可以用他们到根节点的奇偶性来表示！（因为树形结构本身对于根节点来说有某种意义上的差分性质emmm），假如两个点到root的路径长度（也就是depth）奇偶性相同，那么他们之间的路径就是偶数的否则是奇的。所以只需要求出来所有的奇数层的节点个数乘以所有的偶数层的节点个数就可以得到O了。
继续阅读“[比赛][TreeDP][树的性质][换轴][统计技巧] codeforces 1060E Sergey and Subway”
题意给出森林，让在放置的点数尽量少的情况下保证每条边都被点覆盖到（乍一看二分图匹配？），然后在此前提下再要求被两个点同时覆盖到的边最多。两个需要解决的的：1 怎么把这个多目标最优化解决了 2 怎么处理不同节点之间的影响
