一天牛牛整理旧物时发现了一张家谱（家谱可以看做一棵树）。由于年代久远，家谱已经模糊了，现在只能看见人与人之间有直接关系，但是看不出来直接关系是什么了（就是说现在还能直接看出u与v之间有父子关系，但是看不出来是u是v的父亲还是v是u的父亲了）。牛牛还不知道他们家族的最大祖先（根节点）是谁，这样显然就不知道家谱中任意两个人是什么关系了，但是牛牛的爷爷告诉了牛牛家每个人都有多少个孩子（显然叶子节点的孩子数为0），这样就可以推出人与人之间的关系了。家谱中一共有n个人，编号为1~n。牛牛现在有q次询问，对于每个询问，有两个数u和v。对于每组询问输出一行表示他们之间关系。
第一行一个正整数n分别表示家谱中人数 接下来n-1行每行两个正整数w，r，表示w，r是父子关系（但不知道谁是谁的父亲）（即w，r在家谱上有一条边相连）。 接下来一行有n个整数，第i个数代表标号为i的人的孩子的个数 接下来一行一个正整数q表示询问次数 接下来q行，每行两个正整数u，v 2≤ n≤ 2e5,1≤ q≤ 5e5,1≤ u,v≤ n(u!=v)
对于每组询问 如果u是v的祖先，输出“ZZZZ”；（引号不输出） 如果v是u的祖先，输出“SSSS”；（引号不输出） 如果u，v互相都不是另一个人的祖先，则输出他们的最近公共祖先的编号 每组询问输出一行
4 3 4 1 2 3 1 2 0 1 0 3 1 2 4 1 2 4
ZZZZ SSSS 1
考点：树
数据规模 n ≤ 200000 ｜ 限制 4 秒 / 256MB ｜ 标准输入输出
参考方向：树
树结构上的遍历（DFS 求子树信息 / BFS 求层序），多数树题是「后序遍历 + 回溯」。
思路框架（树 通法 · 非本题专属）
实现要点：递归深度可能到 1e5，注意递归爆栈；必要时改迭代或调整递归深度。
复杂度：时间 O(n) ｜ 空间 O(n)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。
样例 1：输入 4 / 3 4 / 1 2 / 3 1 / 2 0 1 0 / 3 / 1 2 / 4 1 / 2 4 → 输出 ZZZZ / SSSS / 1
对于样例，我们可以根据每个人的孩子数以及边的连接方式推出1是根，他有两个孩子2和3，2没有孩子，3有1个孩子4,4没有孩子
第一个询问1是2的祖先，所以输出ZZZZ
第二个询问1是4的祖先，所以输出SSSS
第三个询问2和4互不为对方祖先，他们的最近公共祖先为1，所以输出1
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：贝壳找房2023届校招算法卷2。