树是特殊的DAG图，两者都可以进行DP。

我想讨论如何解决部分复合型算法的DAG图上问题。

约定

按照第一重信息（题面）

第二重信息（可统计）

第三重信息（转移）

顺序讲解。

种树

树上策略性问题，生长速率与天数正相关，如果我们知道种树的天数区间就可以计算。

所以在二分出右区间后（本题有单调性），问题变成判定性问题。

每个区间右端点固定，先计算出满足要求的最大的左端点，同样可以二分。

再作统计，具体点，优先满足树下面的点的要求，因为减少左端点是合法的，而增加不是。

这个计算是统计实际要求的种树时间最晚是那一个数，排序后判断是否都可以操作即可。

总结：通过研究本题要求的单调性想到二分，再使用贪心的方法判断合法。复合型题目都需要研究性质以建模。

运输计划

早年的水题，具有单调性，先用二分转判定性问题。

统计某条边经过了几个路径复杂度很高，但是只统计数量，用树上差分就可以，明显的，我们只能修改一条边所以一条边不能涵盖所有非法路径以及修改后最长边还是非法时不行。

用二分、LCA加树上差分即可。

总结：有时候还会结合Kruskal重构树

函数调用

显然的按照部分分，先处理1、2操作，倒着扫即可，再处理一三操作，建成DAG，维护每一个函数被调用执行次数，最后遍历乘上它加上的数即可。

两个方法结合，先倒着处理，现在的问题是执行了多少次加和乘法与一开始不同，所以倒序处理时遇到函数需要计算贡献，全局乘的贡献也会变化。

我们需要将答案处理为需要将最终的操作转化为一次全局乘，若干次单点加。

所以倒序处理（每个函数无调用），再正序处理（每个函数有调用）

倒序处理也是在处理倒序的乘积，可以处理全局乘。

正序处理的不是一个函数被调用次数，而是他的被调用的值乘以全局乘的值，这可以拿来统计单点加，这是本题难点，我们计算出了后面的全局乘的影响，但是缺少了东西，即由于前面被调用所造成的影响，而另一方面调用后面的值也会对前面造成影响，这个要在前面预处理，即统计子节点的全局乘。

第一次的信息不适用于单点加，但适用于一开始就有的值，以及后面函数所受非调用形全局乘的影响（这个值可以拿来再加上调用所乘的全局乘之后即为受调用的对子节点的贡献（单点加受全局乘的影响）见第二次），再在第二次加上调用的影响即可。

这个想法是通过两点：
1. 单点加操作只会被其后面的全局乘所影响。
2. 前面的调用可以用乘法分配律以计算贡献。

总结：算两次是为了处理两个不同的操作的贡献，它们有依赖关系（不是条件那种），但有时却可以通过分配律等将一个对另一个操作的贡献处理出来，此时只用处理一个操作即可。

Mousetrap

条件复杂的最优化一般会用二分。

但是二分后的判断比前面几题难了很多。

我们需要处理一些信息才可以继续。

往上走和往下走的情况是否可以单列出来讨论呢？

因为本题是一颗树，堵等价于删边，所以树形DP就可以解决往下走的情况。

往上走会难一些，讨论了一下发现等价于枚举老鼠找一个点往下时的第一种情况再加上那个点往上时堵住所有分叉边的情况。

因为堵边代价一样，所以显然是最优情况。

关于往上，则可以结合一开始的二分，如果从一个点下来的代价大于二分值则堵住哪个通道，同一时刻堵不住或已耗尽，则返回wrong。

可以发现，思路与上一题有共通点，先解决一个简单的部分，再解决困难的部分。另一种理解是，将问题化归到熟悉的情况，再扩展。

总结：这一类题可以结合部分分，思维方向不多，但要认真思考不要走错路。

水杯降温

深刻理解前面的解题方法则这题不难。

两类操作的顺序没有要求，因为只用二操作合法的达成条件更难，所以我们考虑达到一操作的达成条件。

处理关于二操作的信息，即一个子树可以用几次二操作。

如此转化为以下问题：

有n堆石子，每次操作等于从石子里各拿一个再选一堆放一个回去，一个堆的石子至多能被选$f_i$次，求最大次数。

如果没有放的操作等于求$min$，否则可以二分后，补足所有差的次数，当然要判断是否大于$f_i$，如果补足的数大于二分数则返回wrong

总结：将题目信息的限制重述出来，对于树上问题可以重述为一个序列问题以便于思考。

迷宫守卫

双方都采取最优策略，显然可以等价于Alice求出石像守卫的最值问题。

预处理出只能走到某个位置的最小代价即可。注意到用map存储即可剪去无效状态。

从上到下再贪心选取即可