AT_arc156_c [ARC156C] Tree and LCS

转化为 \(LIS\) 问题反而还会想复杂.

构造是这样的,每次取出两个叶子,交换权值,删掉.重复这一过程.

考虑为什么是对的,对于每条路径,我们都可以强化限制,将其拓展到两个叶子,你考虑到对于一条路径上的每个结点,要么其权值就与一个不在路径上的点交换,这样肯定不会造成贡献,要么就是与路径上令一个点交换(这样会使整个序列反过来),这样显然也是不造成贡献的.

感觉学到的东西就是从叶子结点考虑问题.