P7518 宝石

题面

见P7518

思路

题意：严格按照$P_1,P_2,P_3,P_4\dots$种宝石的顺序取，每个宝石只取一个，那么最多能取多少？

先看只有从叶子到根的情况：

假如只需要求黑点$s$到紫点$t$这条路径上能得到的最多的宝石。

我们最朴素的想法其实就是求一个路径上的严格单调上升子序列，但是这样复杂度是$O(n)$的，$q$次询问就是$O(nq)$的复杂度，我们是接受不了的。

那么就想想别的法子，怎样能更快、更好呢？

树上倍增倒是挺快的，那我们不妨试试。定义$f_{i,0}$为从编号为i的节点开始拿$2^0$个最近的宝石所到达的位置，假如第$i$号位置的宝石种类为$p_k$，那么下一个拿的宝石就是第$p_{k+1}$种，我们$f_{i,0}$就是该种宝石且离$i$最近的那颗。

如果我们能把所有的$f_{i,0}$给预处理出来，那么就可以倍增求解$f_{s,log({s\to{t})}}$的值了。

那么怎么预处理这个东西呢？

首先我们来用一下树上的 dfs 序，以点$x$根的子树的 dfs 序的范围是$[dfs_x,dfs_x+size_x-1]$，其中$size_x$代表以$x$为根的子树大小，假如$y$在以$x$为根的子树中，当且仅当$y$的 dfs 序在上面这个范围内。

而对于每一个节点，我们都可以预处理出它的 dfs 序的区间，我们把它们当作一个个$node$，并以左端点升序排序（即 子树的根节点的 dfs 序），那么现在就得到了一个左端点单调的序列，现在要在左端点$\le{dfsn_x}$的序列中找满足右端点$\ge{dfsn_x}$的最大左端点，因为左端点最大即代表这个节点越深，那么到$x$是最近的。

而每次在一堆$node$中找右端点最大的那个，这个可以用 ST 表预处理出每个节点对应的$st_{i,j}$表示从$i$号$node$开始走$2^j$个$node$能走到的最大右端点，可以开动态空间来分配每种宝石的 ST 表，然后以单调的左端点进行二分，在所有左端点小于等于$dfsn_x$的$node$中判断右端点是否$\ge{dfsn_x}$，$check()$一下它是否满足条件，如果满足那么左端点就加，直到不能满足为止，那么就可以找到一个满足右端点$\ge{dfsn_x}$的最大的左端点的区间，然后对应到这个区间的根，那么这个根节点就是$f_{x,0}$。

所以这样我们就把从下方的节点到根这样一个单调问题解决了。

那么来看原问题，

例如就是求黑点$s$到蓝点$t$的最大宝石数。

那么就可以把它拆成两段来看：$s\to{lca(s,t)},{lca(s,t)\to{t}}$。

前一段我们已经会了，那么后一段其实就是它的对称情况，我们定义$g_{i,j}$代表从$i$号点开始扔出$j$个宝石的数，假设第$i$号点的宝石种类为$p_k$，那么$g_{i,0}$对应的就是上一个最近的第$p_{k-1}$种宝石的位置，那么剩下的处理方式就和之前一样了，那么最后把$s\to{lca(s,t)}$的$f$值和$t\to{lca(s,t)}$的$g$值加起来就是所求答案，它们可以使用同一个 ST 表。

所以我们就可以进行一个二分答案，二分它最大能得到的宝石数为$x$，假如终点处恰好为第$x$种，那么就可以直接求，假如不是，我们就需要找 dfs 序小于$t$且深度最大的第$x$种宝石的位置。这个位置可以类似预处理$f,g$一样求解，其实就是找在包含$t$的子树中根节点的 dfs 序最大的，不懂请回看预处理。

这样就可以 check 一下在最终得到宝石数为x的情况下是否可能，设$f$倍增到深度小于等于$lca(s,t)$的最大深度为的点选了第$a$种宝石，$g$倍增到深度小于等于$lca(s,t)$的最大深度的点选了第$b$种宝石，假如$a>=b$那么就是满足的，可以继续扩大$x$来二分，直到$b=a+1$这种恰好成立的条件。

最后还要特判一下是否同时跳到了最近公共祖先节点，如果是就还要$-1$，因为同一颗宝石被选了两次。