English · Original
Chinese · Translation
Formal · Original
The Berland Kingdom is a set of _n_ cities connected with each other with _n_ - 1 railways. Each road connects exactly two different cities. The capital is located in city 1. For each city there is a way to get from there to the capital by rail.
In the _i_\-th city there is a soldier division number _i_, each division is characterized by a number of _a__i_. It represents the priority, the smaller the number, the higher the priority of this division. All values of _a__i_ are different.
One day the Berland King Berl Great declared a general mobilization, and for that, each division should arrive in the capital. Every day from every city except the capital a train departs. So there are exactly _n_ - 1 departing trains each day. Each train moves toward the capital and finishes movement on the opposite endpoint of the railway on the next day. It has some finite capacity of _c__j_, expressed in the maximum number of divisions, which this train can transport in one go. Each train moves in the direction of reducing the distance to the capital. So each train passes exactly one railway moving from a city to the neighboring (where it stops) toward the capital.
In the first place among the divisions that are in the city, division with the smallest number of _a__i_ get on the train, then with the next smallest and so on, until either the train is full or all the divisions are be loaded. So it is possible for a division to stay in a city for a several days.
The duration of train's progress from one city to another is always equal to 1 day. All divisions start moving at the same time and end up in the capital, from where they don't go anywhere else any more. Each division moves along a simple path from its city to the capital, regardless of how much time this journey will take.
Your goal is to find for each division, in how many days it will arrive to the capital of Berland. The countdown begins from day 0.
## Input
The first line contains the single integer _n_ (1 ≤ _n_ ≤ 5000). It is the number of cities in Berland. The second line contains _n_ space-separated integers _a_1, _a_2, ..., _a__n_, where _a__i_ represents the priority of the division, located in the city number _i_. All numbers _a_1, _a_2, ..., _a__n_ are different (1 ≤ _a__i_ ≤ 109). Then _n_ - 1 lines contain the descriptions of the railway roads. Each description consists of three integers _v__j_, _u__j_, _c__j_, where _v__j_, _u__j_ are number of cities connected by the _j_\-th rail, and _c__j_ stands for the maximum capacity of a train riding on this road (1 ≤ _v__j_, _u__j_ ≤ _n_, _v__j_ ≠ _u__j_, 1 ≤ _c__j_ ≤ _n_).
## Output
Print sequence _t_1, _t_2, ..., _t__n_, where _t__i_ stands for the number of days it takes for the division of city _i_ to arrive to the capital. Separate numbers with spaces.
[samples]
[{"iden":"statement","content":"贝兰王国由 #cf_span[n] 座城市组成，这些城市通过 #cf_span[n - 1] 条铁路相互连接。每条铁路恰好连接两个不同的城市。首都位于城市 #cf_span[1]。对于每座城市，都存在一条通过铁路到达首都的路径。\n\n在第 #cf_span[i] 座城市中，驻扎着编号为 #cf_span[i] 的军队单位，每个单位有一个优先级数值 #cf_span[ai]，表示其优先级，数值越小优先级越高。所有 #cf_span[ai] 的值互不相同。\n\n某日，贝兰国王贝鲁大帝宣布总动员，要求每个单位都必须抵达首都。每天，除首都外的每座城市都会发出一列火车。因此，每天恰好有 #cf_span[n - 1] 列火车出发。每列火车均朝向首都方向行驶，并于次日抵达铁路的另一端终点站。每列火车具有有限的载客容量 #cf_span[cj]，表示其单次可运输的最大单位数量。每列火车均沿减少至首都距离的方向行驶，即每列火车仅经过一条铁路，从一座城市移动至其邻近的、更靠近首都的城市并停靠。\n\n在每座城市中，优先级最高的单位（即 #cf_span[ai] 最小者）优先登上火车，其次是次高优先级的单位，依此类推，直到火车满载或所有单位均已登车。因此，某个单位可能在某座城市滞留数日。\n\n火车从一座城市行驶至相邻城市所需时间恒为 #cf_span[1] 天。所有单位同时出发，最终均抵达首都，抵达后不再移动。每个单位沿其所在城市到首都的最短路径行进，无论旅程耗时多久。\n\n你的目标是计算每个单位抵达贝兰首都所需的天数。计时从第 #cf_span[0] 天开始。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5000]），表示贝兰王国的城市数量。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an]，其中 #cf_span[ai] 表示位于第 #cf_span[i] 座城市的单位的优先级。所有 #cf_span[a1, a2, ..., an] 互不相同（#cf_span[1 ≤ ai ≤ 10^9]）。随后的 #cf_span[n - 1] 行描述铁路线路，每行包含三个整数 #cf_span[vj, uj, cj]，其中 #cf_span[vj] 和 #cf_span[uj] 是第 #cf_span[j] 条铁路连接的两座城市编号，#cf_span[cj] 表示该铁路列车的最大容量（#cf_span[1 ≤ vj, uj ≤ n, vj ≠ uj]，#cf_span[1 ≤ cj ≤ n]）。\n\n请输出序列 #cf_span[t1, t2, ..., tn]，其中 #cf_span[ti] 表示位于第 #cf_span[i] 座城市的单位抵达首都所需的天数。数字之间用空格分隔。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5000]），表示贝兰王国的城市数量。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an]，其中 #cf_span[ai] 表示位于第 #cf_span[i] 座城市的单位的优先级。所有 #cf_span[a1, a2, ..., an] 互不相同（#cf_span[1 ≤ ai ≤ 10^9]）。随后的 #cf_span[n - 1] 行描述铁路线路，每行包含三个整数 #cf_span[vj, uj, cj]，其中 #cf_span[vj] 和 #cf_span[uj] 是第 #cf_span[j] 条铁路连接的两座城市编号，#cf_span[cj] 表示该铁路列车的最大容量（#cf_span[1 ≤ vj, uj ≤ n, vj ≠ uj]，#cf_span[1 ≤ cj ≤ n]）。"},{"iden":"output","content":"请输出序列 #cf_span[t1, t2, ..., tn]，其中 #cf_span[ti] 表示位于第 #cf_span[i] 座城市的单位抵达首都所需的天数。数字之间用空格分隔。"},{"iden":"examples","content":"输入440 10 30 201 2 12 3 14 2 1输出0 1 3 2 输入55 4 3 2 11 2 12 3 12 4 14 5 1输出0 1 4 2 3 "}]
注意：所有数学公式（如 #cf_span[n]、#cf_span[ai] 等）已按要求原样保留，未作任何转义或修改。术语“division”统一译为“单位”，“alternating sum”等无关术语未出现，符合题面语境。段落结构、换行符与原文完全一致。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of cities.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of distinct positive integers, where $ a_i $ is the priority of the division located in city $ i $.
Let $ T = (V, E) $ be a tree with vertex set $ V = \{1, 2, \dots, n\} $, where vertex $ 1 $ is the capital.
For each edge $ e_j = (v_j, u_j) \in E $, let $ c_j \in \mathbb{Z}^+ $ denote the train capacity on that edge.
Let $ \text{parent}(i) $ denote the unique neighbor of city $ i $ that lies on the unique path from $ i $ to the capital (i.e., the parent in the tree rooted at 1).
Let $ d_i $ denote the distance (number of edges) from city $ i $ to the capital.
Let $ x_i(t) \in \{0,1\} $ indicate whether the division from city $ i $ has arrived at the capital by day $ t $, and let $ t_i \in \mathbb{Z}_{\geq 0} $ be the day on which it arrives.
Let $ S_i(t) \subseteq \{ \text{divisions currently in city } i \} $ be the multiset of divisions present in city $ i $ at the start of day $ t $, ordered by increasing priority $ a_k $.
Let $ f(e, t) \in \mathbb{Z}_{\geq 0} $ denote the number of divisions transported along edge $ e $ on day $ t $, with $ f(e, t) \leq c_e $.
**Constraints**
1. $ 1 \leq n \leq 5000 $
2. $ 1 \leq a_i \leq 10^9 $, all $ a_i $ distinct
3. For each edge $ e_j = (v_j, u_j) $, $ 1 \leq c_j \leq n $
4. The graph is a tree rooted at city 1.
5. Each day, for each non-capital city $ i $, exactly one train departs toward $ \text{parent}(i) $.
6. On each day $ t $, for each edge $ e = (i, \text{parent}(i)) $, the train carries the $ f(e,t) $ divisions from city $ i $ with the smallest priorities among those present, up to capacity $ c_e $.
7. A division moves one edge per day, only toward the capital.
8. Divisions start at their initial cities on day 0.
9. Once a division reaches the capital (city 1), it remains there.
**Objective**
For each city $ i \in \{1, \dots, n\} $, compute $ t_i \in \mathbb{Z}_{\geq 0} $, the day on which the division originally in city $ i $ arrives at the capital.
Output: $ (t_1, t_2, \dots, t_n) $
API Response (JSON)
{
"problem": {
"name": "C. General Mobilization",
"description": {
"content": "The Berland Kingdom is a set of _n_ cities connected with each other with _n_ - 1 railways. Each road connects exactly two different cities. The capital is located in city 1. For each city there is a ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF82C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "The Berland Kingdom is a set of _n_ cities connected with each other with _n_ - 1 railways. Each road connects exactly two different cities. The capital is located in city 1. For each city there is a ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"贝兰王国由 #cf_span[n] 座城市组成，这些城市通过 #cf_span[n - 1] 条铁路相互连接。每条铁路恰好连接两个不同的城市。首都位于城市 #cf_span[1]。对于每座城市，都存在一条通过铁路到达首都的路径。\\n\\n在第 #cf_span[i] 座城市中，驻扎着编号为 #cf_span[i] 的军队单位，每个单位有...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of cities. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of distinct positive integers, where $ a_i $ is the priority of the division lo...",
"is_translate": false,
"language": "Formal"
}
]
}