Tin học trẻ 2021 TPHCM - Vòng Sơ Loại - Bảng C - Lò cò
Xem dạng PDF
Đăng và Nhật đang chơi nhảy lò cò ăn kẹo. Trò chơi được mô tả như sau:
Đăng vẽ ra trên nền nhà ~n~ ~(1 \le n \le 10^5)~ ô vuông và nối một số ô lại với nhau với ~n - 1~ đường nối. Các ô vuông tạo thành một đồ thị vô hướng có dạng cây với đỉnh gốc là ~s~. Một người đứng ở một ô vuông bất kỳ có thể nhảy từ ô này sang ô khác nếu như ô nhảy đến được kết nối với ô người đó đang đứng. Ở mỗi ô vuông, Đăng rải một số lượng kẹo nhất định. Tại ô thứ ~i~ có chứa ~k_i~ viên kẹo. Đăng đố Nhật nhảy lò cò qua các ô để lấy được số lượng kẹo là nhiều nhất.
Trò chơi bắt đầu bằng việc Nhật xuất phát ở đỉnh gốc ~s~. Khi Nhật nhảy sang một ô mới, Nhật lấy đi đúng một viên kẹo tại ô mới đến (không được phép không lấy hay lấy nhiều hơn 1). Nhật có thể di chuyển qua một ô nhiều lần. Tuy nhiên, Nhật không được phép nhảy đến một ô đã hết kẹo, và Nhật bắt buộc phải quay trở lại ô xuất phát ở đỉnh ~s~ để kết thúc trò chơi. Các bạn hãy giúp Nhật tìm số lượng kẹo nhiều nhất Nhật có thể nhặt được.
Yêu cầu:
Hãy viết chương trình tìm số lượng kẹo nhiều nhất Nhật có thể nhặt được.
Dữ liệu:
Nhập từ bàn phím gồm:
- Dòng đầu tiên chứa số nguyên dương ~n (1 \le n \le 10^5)~.
- Dòng thứ 2 chứa ~n~ số nguyên dương ~k_1, k_2, \ldots, k_n~ ~(1 \le k_i \le 10^5)~ , với ~k_i~ là số lượng kẹo tại ô thứ ~i~.
- ~n - 1~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~u~ và ~v~ cho biết ô thứ ~u~ được nối với ô thứ ~v~.
- Dòng cuối cùng chứa đỉnh xuất phát ~s (1 \le s \le n)~.
Kết quả:
In ra màn hình duy nhất một số nguyên là số lượng kẹo nhiều nhất Nhật có thể nhặt được.
Sample Input
6
2 1 3 5 4 6
1 2
1 3
1 4
4 5
4 6
1
Sample Output
12
Sample Input
10
6 4 4 1 3 2 3 7 5 1
1 2
1 5
1 10
2 3
2 6
3 7
3 8
4 5
6 9
1
Sample Output
24
Sample Input
5
1 3 1 2 3
1 4
2 4
3 5
4 5
5
Sample Output
6
Ràng buộc:
- ~20\%~ số điểm của bài tương ứng với các test có ~n \le 50, k_i \le 50~.
- ~60\%~ số điểm khác của bài tương ứng với các test có ~n \le 10^4, k_i \le 10^4~.
- ~20\%~ số điểm còn lại của bài tương ứng với các test có ~n \le 10^5, k_i \le 10^5~.
Bình luận
runtime error luon, mn bt fix sao ko chi minh voi
Bài này mọi người duyệt tìm max ở trong hàm dfs nha!! :))
:))) nói ra việc đó và ngộ thuật là một quảng đường khá xa
quá hay, xin cảm ơn, cho 1 like :))