题目：CF490F
题意解析：给定一棵 nnn 个节点的树，每个节点都有一个点权 AiA_iAi 。求在这棵树所有的路径中点权的 LIS 的最大值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
首先考虑暴力解法。
我们可以枚举每一个节点作为根节点的所有路径 LIS 最大值。
具体做法就是枚举根节点，然后进行 DP，dp[i][j]dp[i][j]dp[i][j] 表示当前 iii 的子树以 jjj 为结尾的 LIS 最大值。
显然可以 O(n)O(n)O(n) 合并信息，总时间复杂度是 O(n3)O(n^3)O(n3)。
此时有两种优化方法：
1. 不从头开始 DP，在以 111 为根的基础上进行换根 DP，可以优化至 O(n2)O(n^2)O(n2)，可以通过。
2. 考虑用更快的方法合并信息。我们可以使用 dsu on tree 方式来实现。O(n2logn)O(n^2\log n)O(n2logn)。
但是仅仅就是这样了吗？
注意到一条经过 iii 的路径可以由两个 iii 的两个子树的路径和 iii 拼成。
所以我们可以求 iii 的子树的 LIS 和 LDS 最大值，然后拼起来。
假设 soni\text{son}_isoni 表示 iii 的所有儿子，lis[i][j]\text{lis}[i][j]lis[i][j] 记录当前 iii 的子树以 jjj 结尾的 LIS 最大值，lds[i][j]\text{lds}[i][j]lds[i][j] 记录 LDS 最大值，则答案为 maxu,v∈soni,u≠v,j<klis[u][j]+lds[v][k]+[j<Ai<k]\max_{u,v\in \text{son}_i,u\not=v,j\lt k} \text{lis}[u][j]+\text{lds}[v][k]+[j\lt A_i\lt
k]maxu,v∈soni ,u=v,j<k lis[u][j]+lds[v][k]+[j<Ai <k]。
直接暴力合并、查询是 O(n2logn)O(n^2\log n)O(n2logn) 的，但是我们可以使用 dsu on tree 来优化至 O(nlog2n)O(n\log^2 n)O(nlog2n) 或 O(nlogn)O(n\log n)O(nlogn)。这里我的方法是 O(nlogn)O(n\log n)O(nlogn) 的线段树合并。
首先 O(nlogn)O(n\log n)O(nlogn) 单独处理 j<Ai<kj\lt A_i\lt kj<Ai <k 的情况，然后合并信息的时候更新所有的答案。
对于当前点 uuu 与 vvv 的区间 [l,r][l,r][l,r]，显然可以按照以下方式更新答案：
* 如果任何一颗树没有记录这颗区间的答案，直接返回。
* 否则令 mid=l+r2mid=\frac{l+r}{2}mid=2l+r ，将 maxj=lmidlis[u][j]+maxj=mid+1rlds[v][j]\max_{j=l}^{mid}\text{lis}[u][j]+\max_{j=mid+1}^{r}\text{lds}[v][j]maxj=lmid lis[u][j]+maxj=mid+1r lds[v][j] 与
maxj=lmidlis[v][j]+maxj=mid+1rlds[u][j]\max_{j=l}^{mid}\text{lis}[v][j]+\max_{j=mid+1}^{r}\text{lds}[u][j]maxj=lmid lis[v][j]+maxj=mid+1r lds[u][j] 更新至答案中。显然这在线段树中对应着节点的左右子树，可以 O(1)O(1)O(1) 更新。
* 向下递归至区间 [l,mid][l,mid][l,mid] 与 [mid+1,r][mid+1,r][mid+1,r]。
* 合并 vvv 的信息至 uuu。
代码如下：
没离散化，时间复杂度 O(nlogV)O(n\log V)O(nlogV)。
由于贺了题解，代码有点诡异（（（
