题解：P8959 「CGOI-3」灵气

· · 题解

闲话

视奸某人做题发现的题，这啥啊，建议降紫。

思路 & 做法

注意到这是一个有向树，并不是一个无向树，也没有内向或者外向的性质，从这里就需要意识到这可能不是常见的树上问题，这种树的性质更少，相应的，需要考虑的处理方向也会变少。

首先抛开修改，分析一下询问。

显然，可以走到 x 的点，在树上并不构成一个区间，也就无法很巧妙地维护，考虑使用强硬一点的方式。

思考在拓扑排序的过程中，如果将一个点的信息传给后继节点，那么每个节点在被取出队列时，都能掌握所有能到达它的点的信息。

这不仅是有向树，更是一个 DAG，将询问离线处理，就能通过进行一次拓扑排序处理出所有答案。

为什么这题不能是一般的 DAG，这是一个好问题，根据平时的积累，容易意识到在 DAG 上进行启发式合并之类的东西的复杂度是错误的，而如果 DAG 是树形图则能保证，进而推测这题使用的可能就是这类做法。

再看修改操作，因为之前已经奠定了离线处理的基调，不妨求出每个点在集合中的时间区间，那么对于一个查询，只需要查询在当前时刻前的每个时刻的最大值，即为历史最大值。

考虑维护这个东西，要求区间修改，最值查询，最重要的是合并，且复杂度正确，那么不难想到使用动态开点线段树，合并则是线段树合并。

想到这些后，这题基本上就做完了，纵观整体，最大的突破点在于问的是有向树上的可达性，不是无向树也不是一般 DAG，显得异常刻意。