Codeforces Round #629 (Div. 3) E – Tree Queries dfs序判祖先关系

惭愧,前几天刚学的dfs序判祖先关系都忘了用。。 这题我们先把所有点都变成父亲节点(根节点不变),这样只需要判所有节点是否在一条链上。 由于判断x是y的祖先:需要满足:st[x]<=st[y]<=ed[y]<=ed[x]. 即:一条链上的的所有点必须是相互包含的关系,一旦有个非链上的点,那么他一定与某个点不是祖先和孙子的关系,就会出现 min(ed[])>max(st[])的情况。 所以我们只需要判断 min(ed[])与max(st[])的关系即可 #include using namespace std; typedef long long ll; const int