Bò Lân Cận

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông trại của Farmer John có $N$ đồng cỏ được kết nối bởi $N - 1$ con đường tạo thành một cái cây. Mỗi đồng cỏ $i$ có $C_{i}$ con bò đang gặm cỏ trên đó.

Farmer John muốn biết, với mỗi đồng cỏ $i$ , có bao nhiêu con bò đang ở trong khoảng cách $K$ cạnh tính từ đồng cỏ $i$ (bao gồm cả bò trên chính đồng cỏ $i$ ).

Dữ liệu vào

Dòng đầu tiên: hai số nguyên $N$ và $K$ .
$N - 1$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $u$ và $v$ mô tả một con đường nối đồng cỏ $u$ và $v$ .
$N$ dòng tiếp theo: dòng thứ $i$ trong số này chứa số nguyên $C_{i}$ — số bò tại đồng cỏ $i$ .

Dữ liệu ra

In ra $N$ dòng. Dòng thứ $i$ chứa $M_{i}$ — tổng số bò trong khoảng cách $K$ cạnh tính từ đồng cỏ $i$ .

Ràng buộc

$1 \leq N \leq 100 000$
$1 \leq K \leq 20$
$0 \leq C_{i} \leq 1000$

Ví dụ

Input	Output	Giải thích
6 2 5 1 3 6 2 4 2 1 3 2 1 2 3 4 5 6	15 21 16 10 8 11	Cây gồm 6 đồng cỏ với $K = 2$ . Đồng cỏ 1 (1 bò) thấy đồng cỏ 2 và 5 (khoảng cách 1) và đồng cỏ 3, 4 (khoảng cách 2). Tổng $M_{1} = 1 + 5 + 2 + 3 + 4 = 15$ .

Ghi chú

Đồng cỏ $u$ và $v$ có khoảng cách $d$ nếu đường đi ngắn nhất trên cây từ $u$ đến $v$ đi qua $d$ cạnh.

Bình luận

Không có bình luận tại thời điểm này.