Editorial

---

E

summary:

모든 노드에 마음대로 $[1,2,\dots,n]$ 순열의 숫자들을 할당한다. 그리고 리프 노드 중 아무거나 제거하고 거기 써 있던 숫자 $x$를 seq에 추가하고, 부모의 숫자가 $x$보다 크면 부모의 숫자를 $x$로 바꾼다.

그렇게 하면 seq는 $n$길이의 수열이 되는데, 거기서 longest non-decreasing sequence의 길이를 구할 수 있다.

가능한 가장 긴 길이를 구하는 문제이다.

solution:

$d[i] = i$를 루트로 가지는 subtree에서 가능한 가장 긴 sequence길이

노드 $i$에 최종적으로 적힐 수가 답에 포함된다고 하면, $i$랑 가장 먼 노드 $j$에서부터 $a_j$가 올라와야 한다. 올라오는 값은 subtree 에서 가장 작은 값이기 때문에 $i$와 $j$사이의 노드들의 형제들이 개입하지 못한다. 따라서 이때의 최적은 $i$에서 가장 먼 노드와 $i$사이 거리이고,

노드 $i$에 최종적으로 적힐 수가 답에 포함 안된다고 하면 a의 자식 노드들은 전부 별개의 seq로 생각하면 되고, $d[i]=\sum_{j \in {i의 자식} }d[j]$이 된다.

opinion:

어차피 i에 적힐 수는 답에 포함이 안 된다고 생각하여 두 번째 경우만 생각했는데, 어떤 수가 쭉 올라와서 non-decreasing한 경우는 생각하지 못했다.