Tổng giá trị trên đường đi từ gốc tới một nút
Mỗi nút của cây có thể mang một giá trị (điểm, chi phí, khối lượng...). Câu hỏi đầu tiên
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Mỗi nút của cây có thể mang một giá trị (điểm, chi phí, khối lượng...). Câu hỏi đầu tiên khi làm việc với giá trị trên cây là: đi từ gốc xuống một nút cho trước thì cộng dồn được bao nhiêu?
Yêu cầu
Cho một cây gồm n nút đánh số từ 1 đến n. Quy ước: nút 1 là gốc của cây, mỗi nút i có một giá trị nguyên a[i], và mỗi cạnh có thể được ghi theo chiều bất kỳ.
Cho thêm một nút t. Hãy tính tổng giá trị của tất cả các nút nằm trên đường đi duy nhất từ gốc 1 tới nút t, tính cả gốc và tính cả nút t. Nếu t = 1 thì đường đi chỉ gồm một nút và đáp án là a[1].
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Chỉ in đúng một số nguyên, không in thêm chữ nào khác.
Input
- Dòng đầu tiên: số nguyên n (1 <= n <= 10).
- Dòng thứ hai: n số nguyên a[1], a[2], ..., a[n] (1 <= a[i] <= 50).
- n - 1 dòng tiếp theo: mỗi dòng hai số nguyên u v là một cạnh của cây.
- Dòng cuối cùng: số nguyên t (1 <= t <= n).
Output
Một số nguyên duy nhất: tổng giá trị trên đường đi từ gốc tới t.
Ràng buộc
- Dữ liệu luôn là một cây hợp lệ: liên thông, đúng n - 1 cạnh, không có cạnh lặp.
- Thứ tự các dòng cạnh là tùy ý, cạnh có thể ghi con trước cha.
- Giá trị các nút là số nguyên dương không vượt quá 50.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
4
5 1 3 2
1 2
1 3
2 4
4
Output
8
Ví dụ 2
Input
1
7
1
Output
7
Giải thích
Dữ liệu vào:
Đường đi từ gốc 1 tới nút 4 là 1 -> 2 -> 4, tổng giá trị là 5 + 1 + 2 = 8. Kết quả in ra là 8.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
