ARC156C 题解

blog。

显然答案为 \(0\) 不行。打表发现最优答案总为 \(1\)。考虑构造取到 \(1\) 的下界。

观察到，\(\text{LCS}\le1\) 等价于去掉两序列都不存在的数后，两序列完全相反。于是有：

• 在 \(\{x\},\{y\}\) 后增加两序列都不存在的数，不影响 LCS。
• 进行 \(\{x\}\to\{a,x,b\},\{y\}\to\{b,x,a\}\) 后，不影响 LCS。

于是每次选两个叶子 \(u,v\) 并将权值赋为 \(v,u\)，再删掉两个点继续做即可。容易归纳证明。

code，时间复杂度 \(O(n)\)，瓶颈在 checker。