51nod1673 树有几多愁（状压DP）

多愁（状压DP）"/>

51nod1673 树有几多愁（状压DP）

传送门

lyk有一棵树，它想给这棵树重标号。
重标号后，这棵树的所有叶子节点的值为它到根的路径上的编号最小的点的编号。
这棵树的烦恼值为所有叶子节点的值的乘积。
lyk想让这棵树的烦恼值最大，你只需输出最大烦恼值对1e9+7取模后的值就可以了。
注意一开始1号节点为根，重标号后这个节点仍然为根。：数据保证叶子节点个数<=20。

题解：状压DP。

首先想到对于每个叶子节点到根节点的链上的标号一定是单调递增的（上面比下面优）。
同时，每个叶子节点到根节点未被标号的路径会一次性被标号，也就是说只要确定了叶子节点的选择顺序，那么整棵树的标号也就确定，因为每次标号会将所有到根的路径上未被标号的点给标号。

证明应该很明显，因为是取到根节点的最小值，假设现在有两条链，设给两条链先后标号的两个min值为 min1,min2 $min_1,min_2$，且 min1 $min_1$为较小值，那么如果同时标号必然会是 min1,min3 $min_1,min_3$，且 min3≤min2</