题解 AT_arc156_c【[ARC156C] Tree and LCS】

· · 题解

首先观察样例大胆猜想答案可能很小，或者就是 1。（不然他答案太大 spj 咋写）

考虑构造证明。

构造方法：对于手上的树，每次取出两个叶子节点交换他们的节点编号作为每个点的权值，然后删掉这两个节点。不断重复此过程。

对于两个叶子节点 (u,v)，权值分别为 v,u。由于两边是等价的取 u 作研究对象。

$u$ 子树的所有点在路径序列出现的位置在 $u$ 之前，在权值序列出现的位置在 $u$ 之后，不可能与 $u$ 一起作为 $\text{LCS}$ 的一部分。 然后就没了。