神仙题Orz
一开始以为是个最小割结果发现不太可做,这题的压缩祖先状态的方法真的神。
我们发现点对的贡献不是很好计算,所以我们考虑计算点的贡献。我们发现本质上付费系数只与 i 和 j 分别与lca的关系有关,也就是这条链的贡献可以转化为两个点对lca的贡献,即链的贡献与 i 和 j 的关系无关。具体贡献看下面。
首先,我们计算一个数组 s[i][j],它的值为 ∑k,lca(i,k)=jFi,k (i 是叶子),我们可以通过枚举点对求出这个数组。那么某一种方案的费用我们就可以用 s 的和来表示。我们现在给非叶子节点也定义状态:对于这个节点的子树,当 nA⩾ 时为状态A,当 n_A<n_B 时为状态 B。那么我们观察收费表可知,当 i 和 j 状态不同(i 是叶子,j 是 i 的祖先)时,s[i][j] 的贡献系数为 1,状态相同时为 0。举个例子,如果现在 n_A<n_B 而且 i 选择的付费方式为 A ,那么 s[i][j] 对答案造成的贡献就是 s[i][j] ,如果是 B ,那么贡献就是 0。如果我们知道了所有点的状态,对每个点和它的所有祖先都这么算一遍,我们就会不重不漏地计算出所有链的贡献(贡献系数为2就是在两个端点处都计算了一次)。
但是如果你直接暴力枚举状态和最朴素的暴力没有区别,我们这么计算贡献是为了方便dp。我们设 f[i][j][k] 为当前dfs到节点 i ,它的子树内共有 j 个选了 B 的叶子节点,它到根节点路径上每个点的状态为 k 。那么当我们dfs到叶子节点时,所有祖先的状态都已知,我们把 \sum s[i][t] 按照贡献系数加入到 f 中,对于非叶子节点,我们只需要枚举左子树内有多少个 B 来更新就好了。就是要注意如果你枚举这个点哪种方案多的时候要保证 B 的个数合法。
这样的话有一个问题:我们开不下数组!所以我们直接在dfs的时候把状态记下来,也就不用开第三维了,也就是我们现在dfs到了一个非叶子节点,我们先把状态设为0,然后dfs子树,更新对应的值,再把状态设为1再dfs一遍子树,给个伪代码:
1 | function dfs(x,l,r) |
这样的话复杂度为 T(n)=4T(\frac{n}{2})+\Theta(n^2) ,根据主定理知 T(n)=\Theta(n^2\log n) ,用这道题里的 n 也就是 \Theta(n2^{2n}) 。
感觉讲的不是很清楚(我语文不好),大家有问题的话看下代码或者留个言,代码还是很好写的就50多行。
代码:
1 |
|
v1.5.2