493 . [Tutorial] 樹的深度 2

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

tutorial

Description

給定一棵有根樹，節點 $1$ 為根且每條邊都有權重。你能計算所有點的深度嗎？一個點的深度為它到根最少要經過的邊權總和。

Input Format

輸入第一行有一個正整數 $n$ 代表樹的節點數量。

接下來 $n - 1$ 行每行有兩個正整數 $u, v, w$，代表節點 $u$ 與節點 $v$ 之間有一條權重為 $w$ 的邊。

  • $1 \leq n \leq 2 \times 10^ 5$
  • $1 \leq u, v \leq n$
  • $1 \leq w \leq 1000$
  • 輸入的圖為一棵樹。

Output Format

輸出一行，該行有 $n$ 個整數 $d_1, d_2, \ldots, d_n$，其中 $d_i$ 代表節點 $i$ 的深度。

Sample Input 1

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

Sample Output 1

0 5 10 16 2 8

Hints

Problem Source

程式解題社教學題。

Subtasks

No. Testdata Range Score
1 0 0
2 0~20 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
Submit
Back to Top