坐看云卷云舒，千纸鹤的折痕在阳光下叠成阴影。
我到底希望着什么？我的目标是什么？
我问我自己。
——————————————————————————————————————————————
链接描述
先分析题目意思：
有NNN个高度互不相同的猫爬架，其高度pi≤Np_i\le Npi ≤N。
有N−1N-1N−1对猫爬架相邻。
初始时，猫猫可以从任意一个猫爬架经过若干次飞跃到达另一个猫爬架。
现在要在猫爬架上放障碍：
如果猫猫不在被选中的猫爬架上，无事发生。
否则：
猫猫会移动到除去当前猫爬架外，高度最大的且可达的猫爬架上，并选择最短路进行飞跃。
“x猫爬架与y猫爬架可达“的定义：若从x开始，不经过任何障碍物，通过若干次飞跃移动到猫爬架y，则称x与y猫爬架可达。
猫猫初始在高度为NNN的猫爬架上。
求猫在整个训练过程中，飞跃次数之和的最大值。
题目解释：
“选择最短路进行飞跃”不是说FLOYD,SPFA,DIJ.
这是树相关的专业用语，即不会在两个点之间来回走，只走一次。
有n−1n-1n−1对猫爬架相邻，可以联想到有n−1n-1n−1条边。
每次从x飞跃到y，都需要保证猫爬架y的高度小于猫爬架x的高度。
子任务分析：
首先能看到，子任务1-12，是一条链。
那么对于一条链，猫要么往左边走，要么往右边走，大概这样：
如果你希望猫往左边走，而此时目标点却在右边，你可以选择在目标点上放置一个障碍物。
然后猫就会往左边走。
也就是说，你可以选择猫往左边走还是往右边边走。
每次你都会有两种选择。
这种感觉有点像归并排序。
归并排序的思想是分治。
那我们就可以考虑，使用分治来解决这个问题。
然后你就可以开始写代码。
代码大概是这样的：
然后发现会有一些超时。
主要超时的原因是找最大值的时候，时间复杂度是O(n)O(n)O(n)。
那么就要考虑如何在短时间内找区间最大值。
先复习一下ST表：
然后将它们合成一下：（注意数据范围变大后要开longlong）
