Tý cần giải bài toán sau:

Trong khu vườn quốc gia có \(N\) địa điểm, giữa các địa điểm có đường mòn đi bộ tạo thành cấu trúc cây. Mỗi địa điểm \(i\) được đánh giá với một giá trị tham quan \(a_i\) (có thể âm nếu địa điểm đó nguy hiểm).

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Một nhóm khách du lịch muốn đi theo một đường đi đơn (mỗi địa điểm chỉ đi qua một lần) sao cho tổng giá trị tham quan của các địa điểm trên đường đi là lớn nhất.

Đầu vào:

• Dòng đầu gồm \(N\).
• Dòng thứ hai gồm \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(|a_i| \le 10^9\)).
• \(N - 1\) dòng sau, mỗi dòng gồm \(u, v\).

Đầu ra:

• Một số nguyên là tổng lớn nhất tìm được.