2021牛客暑期多校训练营7 F.xay loves trees(线段树、树上滑窗)

Description

给两棵树，选取一系列编号的节点，需要满足

• 在树1中节点联通，且互为祖先关系
• 在树2中节点互不为祖先关系

Solution

看了题解，不会他讲的主席树做法，还是感觉树上滑窗的思路好理解。但是很多人说树上滑窗可能会被卡，不是很懂。。。不过仔细一想，如果树上滑窗能被卡，这题应该没那么多人过，可能就被我定义为不可补的题了(

依据题意，在树1中显然是选取一条连续的链，对于树2，可以跑一个 序得到子树的 ，那么可以把子树问题转换成区间相交问题，用线段树来维护。如果加入当前这个点，就等价于加入一个区间。那么就在线段树上区间加 ，如果要查询是否有重合，只需要查询区间最大值，如果大于等于2说明有重合。
在 的过程中维护一个窗口 ，如果出现重合的话肯定不行啦，所以此时窗口的 往后挪动即可，最后在 的过程中记得回溯即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48521166