DRAFT P7518 [省选联考 2021 A/B 卷] 宝石
2026-10-01
简述题意
给定一个长度为 c 且元素互不相同的序列 a,一颗 n 个节点带点权 wu 的无根树,q 次询问,每次给出 (u,v),求最大的 i 使得 a1,a2,…,ai 是 u 到 v 最短简单路径点权构成的序列的一个子序列。
题解
观察到除了在 a 中的颜色都没有用,不妨直接把所有不在 a 中的颜色置为 0,又因为 a 中颜色互不相同,不妨将其设为 ai=i,那么原问题转化为 u 到 v 路径上 1,2,…,c 最多能匹配到哪。
先来考虑 u 到 lca 这一段,考虑令 pu 表示点权为 wu+1 的深度最大的 u 的祖先,那么 u 到 lca 只需要一直跳即可,这可以使用倍增优化。
另一段怎么办?要从 lca 到 v,不妨设 qu 表示点权为 wu−1 的深度最大的 u 的祖先,这样只要从 v 一直跳即可。
