SRM144

Div2-200:水题

Div2-550:模拟题

Div2-1100:树形dp，题意是给定一棵带权树，求遍历完整个树顶点时所走路径长度的最小值。通过分析dfs的过程，可以知道除了最后的一条路径，其他的每个路径上每条边都要走两次，所以答案就是2倍的所有边和减去最长的路径。

Div1-550:数学题。给定1-x和数字，选出其中的y个个数。条件有两个一个是是否非递减序cd1，另外一个是是否允许重复cd2。

两个条件均为假时，显然是x^y

两个条件均为真时，相当于是组合c(x,y)

cd1为假，cd2为真时，相当于全排列A(x,y)

当cd1为真，cd2为假时，即要求可重复的非递减序列时，略微复杂，答案是c(x+y-1,y).可以看做有x个盒子，每个盒子上从左到右依次标记为1-x，每次我们可以选择一个球放入任意一个盒子中，可以允许一个盒子放多个。那么最后各个球所在盒子标号的序列则和这个一一对应。对于这个个数，我的思路是这样的，可能比较繁。

对于n个盒子装m个球，盒子可以为空，也可以装多个。设每个盒子中数量为xk,则xk>=0,且x1+…+xn=m,两边同时加n，有x1+1+…+xn+1=m+n,则相当于有m+n个1，从中插入n-1个挡板，以分成n个大于0的数。所以答案为c(m+n-1,n-1)=c(m+n-1,m).