2020.05.03 2019-2020 ICPC Asia Taipei-Hsinchu Regional Contest pro: 11/11/13
rk: 9/488
AtCoder Beginner Contest 165: F - LIS on Tree
题意是以 1 为根的树,求根到各个节点的路径上,点权的严格最长上升子序列。对每个结点都做并输出。
简单题解:离散化后,DFS 过程中,维护一个以点权为 index 的线段树,value 是以当前 index 作为最后一个值的 LIS,单点修改、区间查极值。每个节点 DFS 结束后恢复一下就好。