0215

今天做了昨天的T3以及去年省选的两个T3。

[模拟赛20230214] 两岸的猿

第二次遇到这种题了。

首先 n^2 dp 是好做的，但是显然不能通过此题。

然后我们可以把dp的转移看成边，然后状态就形成了二维的网格图，然后答案就是图上两点之间的最长路。

然后求解最长路，就可以猫树分治，每次找出一维的中线，计算出跨过中线的答案，然后分治，总复杂度O(n^3)+O(nq)。

这就提示我们多次询问区间的dp，可以考虑转为最长/短路，然后分治计算。（转化为最长路是为了可以往两边dp，然后方便合并）。

学术社区

昨天已经大致写了做法了，但是有一点要记录一下：

isap在这道题的二分图上比dinic慢5倍！！！！！

看来网络流不能无脑isap,反正dinic和isap代码区别不大，可以都试一试。

最大权独立集问题

去年场上想出了三方做法：f(x,i,j) 表示x子树，d(i)出去，d(j)进来，子树的最小代价。然后对于一个点，枚举其操作顺序来转移。

然后考虑如何优化？首先感觉(i,j)这两维都不能省，但是怎么把状态数压到 n^2 呢。思考一下有用的 (i,j) 有多少对，发现确实是O(n^3)，并不能节省状态。但是我们如果对于进子树的权值换一种方式计算：f(x,i,j)表示x子树，d(i)出去 ，进来的值要做j次贡献。这样显然还是能转移，但是有效的(i,j)有多少呢？对于 x,j不大于i的另一个子树的深度+1,于是对于一个i,包含它的总状态只有O(n)个，所以总状态O(n^2)。然后就一样枚举顺序转移即可。