参考这篇博客，本题解作为我的学习笔记。
思路
首先观察到提上说的依赖关系，容易联想到建出一张有向无环图。因为 \(a_i\) 要比 \(b_i\) 先完成，所以从 \(a_i\) 向 \(b_i\) 连一条边。而任务必须从入度为零的点开始依次往下做，因此想到拓扑排序（但题目给的就是拓扑序？）。每次取入度为零的点进行扩展。
以下的图都是拓扑排序后的有向无环图。
一个比较显然的想法是：设 \(dp_v\) 表示到 \(v\) 这个节点时完成任务的最小时间是多少。每次就从连向 \(v\) 的点（设其为 \(u\)）进行转移，如果 \(h_v\) 比 \(dp_u\) 还小，那就说明 \(v\) 必须向后推迟若干天使它大于现在 \(u\) 的天数。答案就是最大 \(dp\) 值减去最小 \(dp\) 值。
但是样例 \(4\) 就 hack 掉了这个做法。为什么呢？我们可以注意到：开始时间是可以我们自己来定的，也就是说可能有些点推迟一些开始会更优。而推迟的点只可能是入度为零的点，因为如果不推迟他们而去推迟他们的后继，只会使答案越来越大。那我们就可以考虑把每个入度为零的点都推迟一天后再进行拓扑排序，但是时间复杂度接受不了。
不过我们可以发现：假如一个点 \(u\) 被往后推迟了一天，被影响的点只会是这个点在图中的所有后继。因为他变大之前他的前驱的值 \(dp_{pre_u}\) 就会比 \(dp_u\) 的值小，他变大之后也一定满足。所以我们只需要考虑 \(u\) 的后继被影响后能变到的最大值。
因为我们主要考虑后推的天数，因此换一种状态。设 \(dp_v\) 表示 \(v\) 这个点最少被推迟多少天。先将每个点原始的 \(dp\) 值都递推出来。
再记一个 \(mx_u\) 表示 \(u\) 推迟一天后 \(u\) 以及 \(next_u\) 被影响后的最大值。有：
\(mx_u=\max \{(dp_u+1)k+h_u,\max \{mx_v \times [dp_u+1+[h_u>h_v]>dp_v] \} \}\)
其中 \(v \in next_u\)，\([]\) 是艾弗森括号。
\(dp_u+1\) 就是 \(u\) 推迟后的天数，如果满足 \(h_u>h_v\)，则 \(v\) 需要再往后推迟一天。因此 \(dp_v=\max \{dp_u+1+[h_u>h_v]\}\)。如果 \(dp_v\) 能被更新到，则 \(mx_u\) 可以从 \(mx_v\) 转移来，因为此时的 \(dp_v\) 值变大，进而影响到所有的 \(dp_{next_v}\)，使 \(mx_v\) 变大。
于是我们可以通过记忆化搜索来实现这一过程。
ll dfs(int u){
if(mx[u]!=-1)return mx[u];
mx[u]=(dp[u]+1)*k+h[u];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(dp[u]+1+(h[u]>h[v])>dp[v])mx[u]=max(mx[u],dfs(v));
}
return mx[u];
}
最后就是统计答案了。我们需要记录一个 \(res\) 表示当前最后一个任务完成的时刻。
首先考虑开始时间就是入度为零的点中最小的 \(h_i\)，此时 \(res\) 就是原始 \(dp\) 数组的 \(\max \{dp_i \times k+h[i] \}\)。
接着考虑把某些入度为零的点推迟后的 \(res\) 如何计算。我们可以把这些点按照他们的 \(h_i\) 从小到大排序得到 \(b\) 数组，于是：
ans=min(ans,res-h[b[i]]);
res=max(res,mx[b[i]]);
因为 \(b\) 是从小到大排的,所以我们可以把每个 \(h[b[i]]\) 当做开始时间，而在它前面的点 \(h\) 值都比他小，因此他们都必须推迟一天后再开始任务，所以 \(res\) 要更新为这些点推迟后的 \(mx\) 值的最大值。动态更新就能求出答案了。