给定一棵以根节点 1 为根的无向树，节点编号为 1,2,...,n ，每个节点 i 的权值为 x_i 。对于每个节点 i(i>1) ： 沿原树从 i 到根 1 的路径，找到离节点 i 最近的第一个权值严格大于 x_i 的祖先节点 j ； 如果 j 存在，在节点 i 与节点 j 之间添加一条额外的无向边；否则，不进行任何操作。 在加入所有额外边之后，计算每个节点到根节点 1 的最短距离（以边数计）。 【名词解释】 祖先节点：在一棵以 u 为根的树中，若点 x 在 u 到 v 的简单路径上，且 x ≠ v ，则称 x 是 v 的祖先节点。根节点没有祖先节点。
第一行输入整数 n(1≤ n≤2×10^5) ，表示节点数量； 第二行输入 n 个整数 x_1,x_2,...,x_n(1≤ x_i≤10^11) ，表示各节点权值； 接下来 n-1 行，每行输入两个整数 u_i,v_i(1≤ u_i,v_i≤ n;u_i≠ v_i) ，表示一条无向边。保证边集构成一棵以 1 为根的树。
在同一行输出 n 个整数 d_1,d_2,...,d_n 以空格分隔，其中 d_i 表示在加入额外边之后，节点 i 到根节点 1 的最短距离。
7 7 1 2 3 4 5 6 1 2 2 3 3 4 5 4 5 6 6 7
0 1 1 1 1 1 1
5 9 6 3 5 4 1 2 1 3 3 4 4 5
0 1 1 1 2
考点：树
数据规模 n ≤ 200000 ｜ 限制 2 秒 / 512MB ｜ 标准输入输出
推荐方向：树
本题切入点
先 DFS 求父子结构，再用「沿根路径维护的单调递减栈」为每个节点找到最近且权值严格更大的祖先并连额外边，最后从根 BFS 求各点最短距离（边权均为 1）。
树结构上的遍历（DFS 求子树信息 / BFS 求层序），多数树题是「后序遍历 + 回溯」。
思路框架（树 通法 · 非本题专属）
实现要点：递归深度可能到 1e5，注意递归爆栈；必要时改迭代或调整递归深度。
复杂度：时间 O(n) ｜ 空间 O(n)
该范式的通法易错点
对照本题
样例 1：输入 7 / 7 1 2 3 4 5 6 / 1 2 / 2 3 / 3 4 / 5 4 / 5 6 / 6 7 → 输出 0 1 1 1 1 1 1
原树是一条链： 1-2-3-4-5-6-7 ，各点权值为 [7,1,2,3,4,5,6] 。
对于每个节点 i>1 1" />，沿原树从 i 到 1 的路径，找到第一个权值严格大于 x_i 的祖先并添加额外边：
节点2：路径 21 ，找到祖先 1 （ 7>1 1" />），添加边 2-1 ；
节点3：路径 321 ，找到祖先 1 （ 7>2 2" />），添加边 3-1 ；
节点4：路径 4321 ，找到祖先 1 （ 7>3 3" />），添加边 4-1 ；
…
添加所有额外边后，节点 2,...,7 均可通过新边直接到达根 1 ，距离均为 1 ；根节点 1 距离为 0 。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2026年春招-美团-算法策略岗-第一批笔试。