非常好的一道题，其实已经想到了正解思想，但被“标号可能重复” 的弱智问题卡住了，没有意识到直接按那个过程做 dfs 即可。

首先考虑编号最大值为平方怎么做，对每个点算出其 与 然后压倒标号里面，回答询问时提取出这些信息就能判断出 在不在某个 的子树内了。

然后发现有很多 的记录是完全没有必要的。设 长度为 （此时我们已经从 中把 的父亲删去），且假设其按照原树的 dfs 序排列，那么对于 ， 的 与 的 的差正好就是 对应节点的 。

那只记录 够不够呢？大部分情况下是够的，对于 小于最后一个儿子的 的情况，我们都能正确回答询问。但问题在于，我们不知道最后一个子树在 dfs 序上的终止位置。

我们知道 本质是每个节点入栈的顺序，那出栈的顺序行不行呢？其实有相似的问题，我们不知道第一个子树在出栈序上的左边界。

考虑问题的本质，设 共有 个邻居，我们的目标无非是将 按照原来的树结构划分成 段（其中 与 相邻），并且通过标号信息快速算出这 段是怎么划的。而在询问的时候，函数给了我们 个信息，即父亲，自己和所有儿子的标号。父亲的标号很难有什么作用，那我们就要把自己和所有儿子的标号全都用上，才能把 区分成至少 个部分。

那为什么之前的 标号只能找到 段呢？本质上是因为对于 的第一个儿子，其 永远等于 ，我们相当于浪费了一个信息。

那考虑把奇数层用入栈序，偶数层用出栈序。注意这里的出入栈序并不指代某个具体的顺序，而是说对于奇数层的节点，其标号为子树中所有标号的最小值，对于偶数层的节点，其标号为子树中所有标号的最大值。 用一个 dfs 即可实现这个过程。这么标完之后，判断 在奇数层还是偶数层其实也是简单的。如果 小于 中的最小值，那在 处显然是先加入的 ，再加入儿子。那么 中最大值就是 的父亲，除开这个值以外的 则是每个子树标号的右边界。此时回答询问就很简单了。反之， 一定大于 中的最大值，也可以同理回答询问。