非常好的一道题，用到了一个重要的思路：消除\(dp\)的后效性
不要觉得这个东西很恐怖，其实这个东西并不复杂，只是名字有点吓人
我们容易想到对把原题抽象成一个图，我们容易想到如果该图为\(DAG\)我们要怎么做，直接拓扑上\(dp\)即可
但回到原题，我们发现\(dp\)就有了一些问题：这个题是有环的，我们对于一个环上的\(dp\)我们无法知道先更新哪一个值，换言之这个\(dp\)是有后效性的。
但我们同时也想到在这个环上一直绕，对答案来说一定是不优的(这里只是感性理解)，但我们并不知道这个绕的策略是什么，因此这个问题让我们很难办
这里有一个重要的思路：消除\(dp\)后效性的方法：
-
先计算部分信息，再通过其他的\(dp\)加加减减，合并到当前信息去：换根\(dp\)就是这个思路
-
如果对于一个\(dp\)出现如果\(dp_u\)更新\(dp_v\)，则\(dp_v\)更新\(dp_u\)绝对不优，则我们改变\(dp\)顺序，再直接\(dp\)
这题用的是第二个思路
我们写出\(dp\)柿子，设\(dp_u\)表示杀死\(u\)点怪兽消耗的最少体力值：
容易得到递推：
\[dp_u = \min{(K_u, S_u + \sum_{i=1}^{R_u}{dp_{v_i}})} \]我们发现什么，我们发现后面这个柿子就满足第二个方法，因为如果存在\(dp_{v_i} \leq dp_{u}\)，则我们一定不会用\(dp_{v_i}\)来更新
因此我们让\(dp_u\)值初始为\(S_u\)，并把所有\(K_u\)的值放到一个堆中，每次用最小的\(dp_u\)值去更新所有指向他的点的、满足\(dp_u \leq dp_v\)的\(dp\)值。如果有一个点的\(dp\)值被更新完了，就把\(dp_u\)放到堆中。这个做法是正确的
-
如果在\(dp_u\)更新完之前使用了\(K_u\)更新其他的点，则说明更新\(dp_u\)一定要用到\(\geq K_u\)的\(dp\)值的点来更新，因此\(K_u < dp_u\)，用\(dp_u\)更新一定不优
-
如果在\(dp_u\)更新完后放到了堆中，但使用了\(K_u\)更新其他的点，则说明\(K_u \leq dp_u\)，同理
-
如果在\(dp_u\)更新完后放入了堆中，且使用了\(dp_u\)更新其他的点，则说明\(K_u \geq dp_u\)，这么做也是不劣的
通过这三种情况，就可以说明这个做法是正确的
最终复杂度\(O(nlogn + \sum{R_i})\)
\(p.s.\)，其实这个思路就是跑\(dijkstra\)，在上面\(dp\)是同一个思路，但\(dijkstra\)的朴素复杂度为\(O(mlogm)\)，但这个题可以保证每个点只在堆中出现一次，因此复杂度可以在包括\(n\)的复杂度
\(p.s.s\)，感谢\(xjk\)提供的解答，使用\(dijkstra\)上跑\(dp\)的前提是这个\(dp\)是有贪心性质的，否则需要使用\(spfa\)。，如这题如果把\(S_u + \sum{dp_{v_i}}\)改成\(S_u + \min{dp_{v_i}}\)，这样\(dijkstra\)显然就不太可做了。
\(p.s.s.s\)，此题中也有部分题解写\(spfa\)做法(而且还能过？)，参考这里
标签：这个,JSOI2014,AHOI2014,更新,dijkstra,复杂度,P4042,我们,dp From： https://www.cnblogs.com/fox-konata/p/17688397.html