BZ OI 队测

T1：

题目大意：

喵星系有n个星球，标号为1到n，星球以及星球间的航线形成一棵树。

所有星球间的双向航线的长度都为1。小昕要在若干个星球建矿石仓库，设立每个仓库的费用为K。对于未设立矿石仓库的星球，设其到一个仓库的距离为i，则将矿石运回的费用为Di。

请你帮它决策最小化费用。n<=200

题解：开始的时候第一眼DP，可是不知道设状态，后来感觉是网络流，但是发现对于仓库哪里无法限流，于是在纠结很久的情况下

　　　想到正解：Tree DP

　　　设一个状态F(x,y)代表第x个点，在y处有个未建仓库，于是对于一个点U和它的子节点V我们可以这样转移：

　　　枚举1--n中的F[V][I]+k的最小值存为Mn，在一次枚举1--n如果F[V][i]>=Mn 那么F(U,i)+=Mn else F(U,i)+=F(V,i)

　　　因为如果F(V,i)>=Mn的话我们完完全全可以新建一个节点，可是这样为什么能保证一个节点新建的费用只算了一次？

　　　那是因为对于建一个仓库它会更优，那么到达它的将是一段连续的点对，那么因为F(U,i)+=F(V,i)，这些点对先会被统计于一个节点

　　　再由这个节点被转移+K，于是保证答案正确性！

T2

题目大意：

小奕和小晟正准备下个周末的Party。为这个Party,他们刚刚买了一个非常大的圆桌。他们想邀请每个人，但他们现在不知道如何分配座次。小奕说当有超过K个女孩座位相邻（即这些女孩的座位是连续的，中间没有男孩）的话，她们就会说一整晚的话而不和其他人聊天。 小晟没有其他选择，只有同意她。然而，作为一名数学家，他很快地痴迷于所有可能方案。 题目说明： N个人围绕着圆桌坐着，其中一些是男孩，另一些是女孩。你的任务是找出所有合法的方案数，使得不超过K个女孩座位是连续的。 循环同构会被认为是同一种方案。

题解：http://files.cnblogs.com/files/HQHQ/%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A_ipsc2008_largeparty.pdf

神犇题解：http://www.cnblogs.com/DUXT/p/5958205.html

T3

题目大意：

Test 17