[APIO2012]派遣

题目大意:有一棵个节点的树,每个节点有一个和一个,同时给定,让你求最大的:

我们需要维护一个堆,能求出枚举每个点时的那些最小的点。

我们将每一个节点看做一棵左偏树,因为,所以我们可以直接自底向上枚举,枚举同时合并子节点。

但是这样由于常数原因依然会超时一部分点,所以我们需要对枚举过程剪枝。

这样考虑,对于每个点,如果其父节点有那么这样的节点一定不优,可以排除。

预处理表示根节点到点路径上的最大值。(这个可以自顶向下处理)。

Code: