I
LYF 签到
H
WD 签到
F
题意：
给定两颗点数相同的、以一号点为根的树，要求一条A树上的不弯折的链(即顶点只选中一个儿子)，使得对应所有点在B树上没有祖先-后代关系。求这样的链的最大长度
ZRC&LYF解：
由于主席树写挂了赛场上一直没过。首先在B树上利用dfn把子树改成区间。然后在A树上dfs。dfs的每一个时刻都对应着一条从根到当前点的链。我们在dfs到当前点时找以当前点结束的最长的链。那么其实问题就变成了如何寻找一个最高的、不会使链中节点在B树中冲突的位置。显然当一个节点出现在链上时，其在B树中的子树即不可选。因此当一个节点正在添加入链时，需要保证该节点不是已存在节点的后代，该节点的后代也不包括链上点。考虑利用主席树区间加1、区间查询（利用和的差是否为0来查询是否加过）来判断节点作为链上最高点是否可行(需要记录父亲这里已经得到的可行链的最高点，对两者取深者)。二分位置。总复杂度O(nlg^2n)
题解的O(nlgn)主席树做法（相当于上面做法的优化）：
在修改主席树时不像上面的+1，而是区间覆盖成当前深度。查询时区间查询最大值即可。
LYF解：
熊高越所谓“树上滑窗”。由于我对滑窗这个名词不熟悉，对双指针比较熟悉，所以我还是更倾向于叫它树上two pointers(手动狗头)。首先，显然如果A树是一条链的话可以利用线段树+双指针求解。然后我们考虑如何在树上推广。主要问题在于当回溯时，线段树的状态也需要回到之前的状态而导致链的上端不断上下跳转而使复杂度出现问题。
考虑如果当前链长为l，那么如果向下dfs的过程中，链长变小了(即链的上端向下移动超过1个结点)，这个答案就不会有意义。因此我们可以在操作中保证链的下移次数不超过当前搜索深度（做法就是每搜一层最多将上端下移一层）。由此，回溯时的修改也是相同复杂度。
故总复杂度O(nlgn)