E. Hanging Hearts
Pak Chanek has $n$ blank heart-shaped cards. Card $1$ is attached directly to the wall while each of the other cards is hanging onto exactly one other card by a piece of string. Specifically, card $i$ $(i>1)$ is hanging onto card $p_i$ $(p_i<i)$.
In the very beginning, Pak Chanek must write one integer number on each card. He does this by choosing any permutation $a$ of $[1,2, \ldots ,n]$. Then, the number written on card $i$ is $a_i$.
After that, Pak Chanek must do the following operation $n$ times while maintaining a sequence $s$ (which is initially empty):
- Choose a card $x$ such that no other cards are hanging onto it.
- Append the number written on card $x$ to the end of $s$.
- If $x \ne 1$ and the number on card $p_x$ is larger than the number on card $x$, replace the number on card $p_x$ with the number on card $x$.
- Remove card $x$.
After that, Pak Chanek will have a sequence $s$ with $n$ elements. What is the maximum length of the longest non-decreasing subsequence$^\dagger$ of $s$ at the end if Pak Chanek does all the steps optimally?
$^\dagger$ A sequence $b$ is a subsequence of a sequence $c$ if $b$ can be obtained from $c$ by deletion of several (possibly, zero or all) elements. For example, $[3,1]$ is a subsequence of $[3,2,1]$, $[4,3,1]$ and $[3,1]$, but not $[1,3,3,7]$ and $[3,10,4]$.
Input
The first line contains a single integer $n$ $(2 \leq n \leq {10}^{5})$ — the number of heart-shaped cards.
The second line contains $n−1$ integers $p_2,p_3, \ldots ,p_n$ $(1 \leq p_i < i)$ describing which card that each card hangs onto.
Output
Print a single integer — the maximum length of the longest non-decreasing subsequence of $s$ at the end if Pak Chanek does all the steps optimally.
Examples
input
6 1 2 1 4 2
output
4
input
2 1
output
2
Note
The following is the structure of the cards in the first example.
Pak Chanek can choose the permutation $a=[1,5,4,3,2,6]$.
Let $w_i$ be the number written on card $i$. Initially, $w_i=a_i$. Pak Chanek can do the following operations in order:
- Select card $5$. Append $w_5=2$ to the end of $s$. As $w_4>w_5$, the value of $w_4$ becomes $2$. Remove card $5$. After this operation, $s=[2]$.
- Select card $6$. Append $w_6=6$ to the end of $s$. As $w_2≤w_6$, the value of $w_2$ is left unchanged. Remove card $6$. After this operation, $s=[2,6]$.
- Select card $4$. Append $w_4=2$ to the end of $s$. As $w_1≤w_4$, the value of $w_1$ is left unchanged. Remove card $4$. After this operation, $s=[2,6,2]$.
- Select card $3$. Append $w_3=4$ to the end of $s$. As $w_2>w_3$, the value of $w_2$ becomes $4$. Remove card $3$. After this operation, $s=[2,6,2,4]$.
- Select card $2$. Append $w_2=4$ to the end of $s$. As $w_1 \leq w_2$, the value of $w_1$ is left unchanged. Remove card $2$. After this operation, $s=[2,6,2,4,4]$.
- Select card $1$. Append $w_1=1$ to the end of $s$. Remove card $1$. After this operation, $s=[2,6,2,4,4,1]$.
One of the longest non-decreasing subsequences of $s=[2,6,2,4,4,1]$ is $[2,2,4,4]$. Thus, the length of the longest non-decreasing subsequence of $s$ is $4$. It can be proven that this is indeed the maximum possible length.
解题思路
关键性质，对于某棵子树，得到的序列的最后一个元素必然是该子树的根节点，同时这个值是整棵子树中的最小值。
对于最优解，对应的树的父节点的值一定比子节点的值都要大。否则如果一颗树存在某个子树的根节点比它的某个儿子的值要小，那么我们就交换两个节点的值，在得到的序列中这个子节点所对应的值一定会变小，而根节点的值不变，因此得到的结果不会变差，即最长非递减子序列只会变长而不会变短。因此只要存在某个父节点比子节点的值要大，那么就交换，最后整棵树的父节点都会比子节点要大。
因此对于某棵子树所得到的所有序列我们可以根据是否选择这个子树的根（也就是序列的最后一个元素）来分成两大类。定义$f(u, 0)$表示以$u$为根的子树中，不选择根节点$u$的所有序列；$f(u, 1)$表示以$u$为根的子树中，选择根节点$u$的所有序列。属性是序列的非递减子序列长度的最大值。
如果选择序列中包含根节点，由于此时根节点的值是整棵子树中的最小值，因此最长的非递减子序列的值必然也是整棵子树中的最小值，因此我们可以贪心地构造，找到这棵子树从根节点开始的最长路径，然后这条路径的叶子节点定义为整棵子树的最小值，那么非递减子序列长度的最大值就是整棵子树的最长路径。$f(u, 1) = \max\limits_{v \, := \, \text{all son}}\{f(v, 1)\}$。
如果选择序列中不包含根节点，对于某棵子树的根节点，以其各个子节点为根的子树所得到的序列都是相互独立的，因为它们之间的删除顺序不会互相干扰，因此最后所有以各个子节点为根的子树所得到的序列是可以任意合并的，同时我们也可以单独来求各个以子节点为根的子树的非递减子序列。由于可以任意组合各个子树所得到的序列，因此我们可以贪心地来按照非递减的方式来合并以得到最长的非递减子序列。$f(u, 0) = \sum\limits_{v \, := \, \text{all son}} \max\{f(v, 0), f(v, 1)\}$。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 1e5 + 10;
5
6 int head[N], e[N], ne[N], idx;
7 int f[N][2];
8
9 void add(int v, int w) {
10 e[idx] = w, ne[idx] = head[v], head[v] = idx++;
11 }
12
13 void dfs(int u) {
14 f[u][1] = 1;
15 for (int i = head[u]; i != -1; i = ne[i]) {
16 dfs(e[i]);
17 f[u][0] += max(f[e[i]][0], f[e[i]][1]);
18 f[u][1] = max(f[u][1], f[e[i]][1] + 1);
19 }
20 }
21
22 int main() {
23 int n;
24 scanf("%d", &n);
25 memset(head, -1, sizeof(head));
26 for (int i = 2; i <= n; i++) {
27 int p;
28 scanf("%d", &p);
29 add(p, i);
30 }
31 dfs(1);
32 printf("%d", max(f[1][0], f[1][1]));
33
34 return 0;
35 }
参考资料
Codeforces Round #831 (Div. 1 + Div. 2) A~F：https://zhuanlan.zhihu.com/p/579511116
标签：子树,int,number,Hanging,序列,Hearts,节点,card From： https://www.cnblogs.com/onlyblues/p/16904820.html