原题题解似乎是两个 $\log$，提供一个单 $\log$ 的爆标做法。

随便固定一个根，考虑如果要求每一步都走向子树内怎么办。

设 $f_u$ 表示 $u$ 走向子树内的路径的最长 LIS 长度，按 $a_u$ 从大到小的顺序加入所有节点即可。转移是单点修改、查询子树最大值，可以简单线段树维护。

现在还需要求出子树外的情况。设 $g_u$ 表示 $u$ 走向子树外的路径的最长 LIS 长度。它的转移有以下几类：

• 对于和 $u$ 没有祖先后代关系的一个点 $x$，用 $h_x$ 来转移。
• 对于 $u$ 到根的祖先链上的一个点 $x$，从它向 $u$ 以外的方向的路径的最长 LIS 长度，来转移。

对于第一类，分讨一下可以发现限制就是 $dfn_u > dfn_x + siz_x - 1$ 或 $dfn_x > dfn_u + siz_u - 1$。维护两棵值域线段树就可以。

对于第二类，我们发现只用 $g_x$ 来转移是不够的。于是考虑设 $h_u$ 表示 $fa_u$ 走向 $u$ 子树外的路径的最长 LIS 长度。

那么 $h_u$ 的转移也很简单，要么是从和 $u$ 没有祖先后代关系的点 $x$ 的 $f_x$ 转移，要么是从祖先链上的其他 $h_x$ 转移。

直接写出来是 $O(n \log^2 n)$ 的，因为我们要查询一条祖先链上的 $h_x$ 的最大值，需要使用树剖。但我们可以将单点修改链查询，转化为子树覆盖单点查询。同样使用线段树维护即可。这样就做到了 $O(n \log n)$。