루미 알고리즘

#1563다이아The Generous Traveler

PO 2023 훈련 캠프코딩출제 Abdullah Zaghmout영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Your rich friend Erika lives in a country with N villages where the i:th village has A_i inhabitants. The villages are connected with N-1 roads such that it is possible to travel from any village to any other village using these roads.

After a whole day of work, Erika is exhausted and needs to go on vacation, so she plans to visit some of the country's villages. As with all rich people, there is nothing your friend likes more than giving away money! Therefore, she plans to take a big bag of coins and give away as much money as she can in each village she visits (including the one she starts in).

However, there is a problem: if an inhabitant of a village receives less money than another inhabitant in the same village, they become very angry, and Erika's life is threatened. To avoid this, she decides to give all inhabitants as much money as she can so that everyone in the same village gets the same amount, even if it means no one gets any money.

Now, Erika wonders how much money she will have left at the end of such a trip. She asks you Q questions of the form: Given that the trip starts at village u with x coins, and ends at village v, how much money will be left at the end of the trip?

Note that the trip always follows the simple path between two villages, i.e., the unique shortest path. Erika only gives out whole coins, so she always gives a non-negative integer amount of money to each villager.

Input

The first line contains the two integers N (1 ≤ N ≤ 2 · 10^5) and Q (1 ≤ Q ≤ 10^5).

Then follow N-1 lines, where the i-th line contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ N). This means that there is a road between villages a_i and b_i.

The next line contains N integers A_1, A_2, …, A_N (1 ≤ A_i ≤ 10^9), each describing the number of inhabitants in village i.

Finally, there are Q lines, one per query. The i-th line consists of integers u_i, v_i, x_i (1 ≤ u_i, v_i ≤ N, 1 ≤ x_i ≤ 10^9), where u_i is the starting village, v_i is the ending village, and x_i is the number of coins Erika starts with in the i-th query.

Output

For each query, print the answer on its own line.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
110N,Q ≤ 2000
220There is a path between village i and village i+1 for all 1 ≤ i ≤ N-1, A_i ≤ 100.
325There is a path between village i and village i+1 for all 1 ≤ i ≤ N-1.
425All trips end at village 1. Formally, v_i=1 for all 1 ≤ i ≤ Q.
520No additional constraints.

Explanation of sample

In the first test case, the first journey occurs between village 8 and village 10, and Erika starts with 31 kronor. Already in the first village (with 20 inhabitants), she gives away 1 krona to each person, and has 11 left. The journey then continues to village 7, with 10 inhabitants. Here too, Erika gives away one krona to each person, and now only has one krona left. Finally, Erika reaches village 10, with 20 inhabitants. Unfortunately, Erika can't afford to give any money to the population here, so she ends up with 1 krona left.

The second test case is an example of a test case that can appear in test case groups 1, 2, and 3.

예제

예제 1

입력
10 7
1 2
2 5
5 3
2 6
6 7
7 8
7 10
1 4
1 9
5 8 10 10 9 5 10 20 3 20
8 10 31
3 9 5
3 9 14
8 3 34
1 6 8
7 2 19
10 4 43
출력
1
0
1
4
3
4
3

예제 2

입력
4 3
1 2
3 2
3 4
5 2 7 4
1 1 9
3 2 11
2 3 11
출력
4
0
1

출처 표기

출처: Programmeringsolympiaden 2023년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.