牛客多校7.F.xay loves trees 主席树+dfs序

Problem Ananlysis

题目给定两棵根编号为 1 1 1​的树，求一个满足以下要求的最大集合

1. 第一棵树上的任意两个元素具有祖先后代关系
2. 第二棵树上的任意两个元素不具有祖先后代关系

我们可以发现，满足以上两条关系的实际上就是：

1. 这些元素在第一棵树中是从上到下的一条链(允许非连续)

2. 这些元素在第二棵树中，任意两个元素，不能在从上到下的一条链中

我们首先来回顾 d f s dfs dfs​序的知识： d f s dfs dfs序，顾名思义即为 d f s dfs dfs遍历的顺序(时间顺序)。我们用两个数组 i n [ ] 、 o u t [ ] in[]、out[] in[]、out[]， i n [ i ] 、 o u t [ i ] in[i]、out[i] in[i]、out[i]分别表示某个点被 d f s dfs dfs​进入的时间点、该点回溯时的时间点。

很显然，对于某点的子树而言，一定存在“晚入早出”的关系：点 A A A​的子节点 x x x的 i n [ x ] in[x] in[x]​值一定要比 i n [ A ] in[A] in[A]大， o u t [ x ] out[x] out[x]一定比 o u t [ A ] out[A] out[A]​小，利用这个性质，我们可以很轻松的找到某个点的子节点。

此外，还有一条重要性质：一棵树上的 d f s dfs dfs序入点和出点一定是连续的。

利用上面的性质，我们可以继续转化问题：

在第二棵树的 d f s dfs dfs序上找尽可能多的连续区间，满足①.互不相交；②在第一颗树上位于同一条链上。

对于第一棵树，我们继续讨论如何维护链信息：容易想到维护一个栈， d f s dfs dfs​到该点时入栈，回溯时出栈，这样就可保证栈内的点均为同一条链上的点。

然后对于第二棵树，我们跑出其 d f s dfs dfs序后，在第一颗树的 d f s dfs dfs遍历过程中，加入点的时候将其子树的点区间增加 1 1 1​​。这样下次加入节点只需要判断待加入的节点在树上是否有值即可。

所以我们可以对每个点建立主席树，

此外我们需要定义数组 m a x n [ x ] maxn[x] maxn[x]表示 x x x节点向上找，最后一个符合条件的点序号。

那么只需要在 m a x n [ f a ] maxn[fa] maxn[fa]和 n o w now now范围内不断二分寻找满足第二棵树的点，然后更新答案即可。

#include 
using namespace std;

const int N = 1e6 + 10;

int root[N], ls[N  u >> v;
            G1[u].push_back(v);
            G1[v].push_back(u);
        }
        for (int i = 1, u, v; i > u >> v;
            G2[u].push_back(v);
            G2[v].push_back(u);
        }
        dfs1(1, 0);
        dfs2(1, 0);
        cout