BZOJ5250: [2018多省省队联测]秘密袭击

原题链接

Solution

先看一份官方题解:秘密袭击simple

然而作为一个连FFT都不会的蒟蒻,又怎么可能在只有五小时,写完前两题的情况下做出这题呢?

所以是时候用暴力吊标算了。

考虑枚举每个点,算出这个点作为第k大时对答案的贡献。如果直接算,可能会算重。
我们可以定义:u的权值大于v当且仅当d[u]>d[v]||(d[u]==d[v]&&u>v),记为$u\rhd v$,即d相同时比较两点的编号。

如果枚举一个点u作为第k大点,那么可以从u开始进行树形DP。
设f[u][k]表示以u为根的子树,选了点u,并且选出的联通块中有k个点权值大于根。

有个很显然的转移:$Sum[u][k]=\sum_{i=0}^{k}f[v][i]*Sum[u][k-i]$
则$f[u][k+(u\rhd root)]=Sum[u][k]$,
这样的树形DP复杂度为$O(n^3)$(n,k同阶),总复杂度为$O(n^4)$。很不幸,不能吊标算

请看陈俊锟在WC2018讲课的三页PDF



用上面的方法,就可以优化这个DP,使一次树形DP的复杂度变为$O(n^2)$(具体看代码),总的复杂度为$O(n^3)$,再加上一点玄学优化(不要告诉我底层优化),就能过了,实测在LOJ上最慢的点为1.8s。

Code

0 条评论
发表一条评论