Tin học trẻ 2021 TPHCM - Vòng Sơ Loại - Bảng C - Lò cò

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
Tin học trẻ 2021 TPHCM - Vòng Sơ Loại - Bảng C
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đă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~.

Comments

Please read the guidelines before commenting.



  • 0
    Giangcoder   commented on May 15, 2022, 7:56 p.m.

    Bài này mọi người duyệt tìm max ở trong hàm dfs nha!! :))


    • 1
      LeThanhMinh   commented on May 29, 2022, 7:32 p.m.

      :))) nói ra việc đó và ngộ thuật là một quảng đường khá xa


    • -5
      vdlong   commented on May 27, 2022, 8:49 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.