https://codeforces.com/problemset/problem/2002/D2
考虑找一个容易维护的必要条件，再证明充分性。最容易想到的是
每个子树对应一个区间，子树根位于左端点
sol 1
相邻的结点 \(p_{i-1},p_i\) 有两种情况：\(fa[p_i]=p_{i-1}\)；叶子 \(p_{i-1}\) 在子树 \(fa[p_i]\) 中，回溯到 \(fa[p_i]\)（\(fa[p_i]\) 的 \(p_{i-1}\) 方向的子树搜完了），再递归到 \(p_i\)
事实上不需要括号中的条件
\(p_1=1\)，\(p_{i-1}\) 在子树 \(fa[p_i]\) 中
Pf. 对于子树 \(u\)，满足 \(p_{i-1}\) 不在子树 \(u\) 中且 \(p_i\) 在子树 \(u\) 中的位置只有一个 \(p_i=u\)（只有子树 \(fa[u]\) 中有不在子树 \(u\) 中的点）
时间复杂度 \(O(n+q)\)
sol 2
父子 \(u,v\) 满足 \(dfn[u]<dfn[v]\land dfn[v]+siz[v]-1\le dfn[u]+siz[u]-1\)
Pf. 自下而上归纳证明每个子树都合法
只需要 check \(\min\{dfn[v]\},max\{dfn[v]+siz[v]-1\}\)，multiset 维护
时间复杂度 \(O((n+q)\log n)\)
标签：子树,题解,复杂度,Hard,sol,DFS,fa,dfn From： https://www.cnblogs.com/ft61/p/18402281