首先宝石一定是能吃就吃，先吃一定不劣。
如果你足够细心，应该可以发现 \(p_i\) 是互不相等的。
这有什么用呢？设 \(a_i\) 表示 \(w_i\) 在 \(p\) 中的出现位置（\(p_{a_i} = w_i\)）。如果我们选了 \(a_i\)，那么下一个要选的一定是 \(a_i + 1\)（废话）。
具体的，我们将 \(u \rightarrow v\) 拆成两条链：\(u \rightarrow lca, lca \rightarrow u\)。（一条向上，一条向下）
对于 \(s \rightarrow lca\)，找到 \(s\) 的第一个出售 \(p_1\) 祖先的 \(x_1\)，然后找到 \(x_1\) 第一个出售 \(p_2\) 的祖先 \(x_2\)，以此类推，直至 \(dep_{x_i} < dep_{lca}\)。
这就用到前面说的那个性质，对于某个 \(x_i\)，对应的 \(x_{i + 1}\) 是确定的（\(x_i\) 第一个出售 \(a_{i} + 1\) 的祖先）。
于是就可以使用倍增优化这个向上跳的过程，令 \(f_{u, i}\) 表示 \(u\) 向上跳 \(2^i\) 步到达的位置。对于形如求 \(u\) 的第一个出售 \(p_k\) 的祖先 \(F(u, k)\)，可以使用主席树求解。那么 \(f_{u, 0} = F(u, a_u + 1)\)。
于是我们就可以快速算出往上跳的部分获得了 \(cnt\) 宝石（从 \(F(u, 1)\) 开始倍增的往上跳即可），难点在于向下跳。因为向下跳是不知道下一次会跳到什么地方的。（有一堆儿子。）但是我们可以尝试转化成向上跳。
但是有个问题，我们连最后一个宝石都不知道，也就是连往上的第一个位置都不知道（向上跳的部分第一个就是 \(F(u, 1)\)）。这时我们就可以二分答案 \(mid\)，表示最后一个获得的宝石类型是 \(mid\)，那么向上跳的第一个位置是 \(F(v, mid)\)。
接下来就和向上跳的部分类似了，设 \(g_{v, i}\) 表示 \(v\) 向上跳 \(2^i\) 步的位置，只不过 \(g_{v, 0} = F(v, a_{v} - 1)\) 而已。check 时只需要判断 \(F(v,mid)\) 向上跳 \(mid - 1 - cnt\) 步得到的节点深度是否 $ > dep_{lca}$ 即可。
时间复杂度：\(O(q \log^2 c)\)。
难点在于想到如何利用好 \(p_i\) 互不相同的条件，得到 \(x_i\) 对应 \(x_{i + 1}\) 是确定的，从而倍增的优化向上跳的部分。以及对于向下跳的部分，如何转换成向上跳的部分，配合二分求解。