最好的位置

Problem Description

小 E 居住在一棵树上，ta 发现此时正是果实成熟的时节。 这棵树包含 $n$ 个节点，编号为 $1$ 到 $n$，每条边长度为 $1$。 每个节点 $i$ 都被赋予了一个唯一的权值 $w_i$。这些权值恰好是 $0$ 到 $n-1$ 的一个排列。代表这些果实成熟的时刻。 现在，为了方便采摘，小 E 定义一系列动态增长的节点集合:

• 对于每个 $m=0,1,\dots, n-1$，定义节点集合 $S_m$ 为所有权值小于或等于 $m$ 的节点的集合。即：$S_m =$ {$u \mid w_u \leq m$}。表示时刻 $m$ 成熟果子节点集合。
• 对于每一个集合 $S_m$，你需要找到一个“最佳采摘点” $x$ 和一个“最小覆盖半径” $k$，使得所有在 $S_m$ 中的节点都位于以 $x$ 为中心、$k$ 为半径的“邻域”内（即对于所有 $u \in S_m$，都有 $\text{dist} [x, u] \leq k$）。节点 $x$ 可以是树上的任意一个节点（不一定在 $S_m$ 中）。 你的任务是，对于每个 $m$（从 $0$ 到 $n-1$），计算出这个最小的覆盖半径 $k$。

Input

本题有多组测试数据。第一行一个正整数 $T$，表示数据组数，接下来输入每组测试数据。 对于每组测试数据：

• 第一行包含一个正整数 $n$。
• 第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$，表示每个节点果实成熟时间。输入保证这是一个 $0$ 到 $n-1$ 的排列。
• 接下来的 $n-1$ 行，每行包含两个整数 $u, v$，表示一条连接节点 $u$ 和 $v$ 的边，长度为 $1$。

Output

对于每组数据，输出 $n$ 行，每行一个正整数，第 $i$ 行表示 $S_{i-1}$ 的最小覆盖半径。

Sample Input

3
6
4 3 1 0 2 5
5 1
6 2
2 3
1 2
3 4
6
5 3 4 2 0 1
4 3
1 2
3 2
4 6
1 5
6
4 1 2 3 5 0
4 6
3 4
1 2
3 2
5 1

Sample Output

0
1
2
2
2
2
0
3
3
3
3
3
0
2
2
2
2
3

Hint

对于全部数据，$T\leq 10，2\leq n\leq 2\times 10^5, 0\leq w_i<n, 1\leq u,v\leq n$，保证输入是一棵树，$w$ 是 $0\sim n-1$ 的全排列。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（8）