一些题目

昨天duel了好多题，记一下。

Hanging Hearts

这题一看很复杂，又是树形结构，我们考虑用树形DP解决。

那么就只用考虑当前子树的关系了。

要让最长不下降子序列长度最大，我们先想想什么情况会让最长不下降子序列长度变大。

那就是\(f_i\)可以从\(f_j,j<i,a_j \le a_i\) 的地方转移过来。

这个时候题目中的操作3不禁让人联想到树剖、倍增LCA、……中的swap操作，它们都是保证了形如\(x \le y, x \ge y\)的关系式。

看起来和\(a_j \le a_i\)就很有关系。

具体来看，操作3使得\(w_{p_x} \le w_x\)。

又因为每次只是选择叶子，所以\(p_x\)必然在\(x\)后面被选择，也就是说，在\(s\)中，\(w_{p_x}\)出现在\(w_x\)的后面。

那其实\(w_{p_x}\)就对应了\(a_i\)，而\(w_x\)就对应了\(a_j\)（这只是感性猜想）。

树形DP的有一个方法，就是先考虑序列问题，然后将序列问题中讨论最后一个点的部分替换为讨论根节点。

最长不下降子序列问题中，讨论的是以最后一个数结尾的子序列。

这就启发我们讨论根是否在子序列中。

假如根不在子序列中，因为权值可以随意分配，一个直观的想法是可以把所有子树的贡献累加起来。

设\(f_u\)是\(T_u\)中的最长不下降子序列的最大长度。

这是一个上界，也就是\(f_u \le sum\)。假设\(f_u > sum\)，就必然存在一个子树 \(T_v\)，它的贡献比 \(f_v\) 还要多，这就矛盾了。

然后我们发现只要依次从小到大赋值子树然后依次选取，就可以达到这个上界。

所以这就是这种情况的答案。

假如根在子序列中。

由于上面\(w_{p_x} \le w_x\)的性质，根要接在子树中某个点的后面，构成一个更长的子序列，就必须有\(w_u \ge w_k\)。

放缩一下\(w_u \le w_v \le ... \le w_k\)。所以\(w_u = w_v = ... = w_k\)。所以可以把它到根的链上的点加入贡献。

然后你发现，只有操作3能够使得这个连等式成立，而操作3的条件就是父亲大于儿子，所以我们让根在最长链上权值从大到小依次赋值（让根的值大于该链上的所有值）就可以有链长的贡献。

模拟一下会发现，貌似不可能有两条链同时有贡献。

假设有两条链都有贡献，\(i,j\)分别为它们深度最大的点，因为\(u\)一定在子序列中，所以\(w_u=...=w_i\)，\(w_u=...=w_j\)。

因为\(i,j\)是深度最大的点，也就是\(w_i=a_i,w_j=a_j\)（否则它们是从自己儿子交换来的，儿子深度更大，矛盾）。

\(a_i=a_j\)，矛盾。

然后答案就是最长链的长度。