题外话

这题....真jay形!

简述题意

由于codevs和bzoj上的题意都不完整,在此简述题意( ~~然而再怎么简述这个题意都很长啊~~ )。
一棵满二叉树的叶子节点是用户,网络公司很jay形,要求捆绑收费,对于每一对用户i,j,要收的费用是w[i][j]×k,w[i][j]会在输入数据里给出,而k的定义是:
找到i和j的最近公共祖先p,以p为根的子树里选择A收费方式的用户数为$n_a$,选择B收费方式的用户数为$n_b$。假如$n_a$小于$n_b$,那么1A1B的话k=1,全B为2,全A为0。否则1A1B对应K=1,全B为0,全A为2
所有用户已经选了收费方式,如果要修改就要交钱。第i个用户的修改费用为c[i]( ~~居然还区别对待有没有天理有没有人性!~~ ),求修改一些人后交的费用最少值。

题目分析

对于一棵以k为根的子树,假如$n_a$<$n_b$,这个点就标记为B点,否则这个点就标记为A点,那么对于一个点i,假设它是A,它的一个祖先j是A,那么这个节点就需要交所有和它的祖先是j的所有节点k的w[i][k]的总和的钱,这个总和可以预处理出来。
那么我们可以这样,用$f(x,num,zt)$表示以x节点为根的子树上,有num个A节点,其所有祖先的状态用状压表示为zt的最少交的钱数,对于叶子节点,我们可以根据zt来特殊考虑$f(x,num,zt)$的值,其他的状态转移方程为:
$$f(x,num,zt)=min(f(left,i,zt+s)+f(right,num-i,zt+s));$$
s表示当前x节点的状态是A还是B
然而这样空间无法承受,我们可以再压一维,就是用一种神奇的方式把后面两维的状态合并,具体看代码。

代码