Cây - được định nghĩa là một đồ thị vô hướng liên thông gồm n đỉnh và không có chu trình. Cho một đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh, nếu đó là một cây thì in ra "Yes", ngược lại in ra "No".

Input:

• Dòng đầu gồm 2 số ~n~ và ~m~. ~(2 \le n, m \le 1e5).~
• ~m~ dòng sau, mỗi dòng gồm 2 số ~u,v (1 \le u, v \le n)~ chỉ ra tồn tại một cạnh vô hướng giữa 2 đỉnh này.

Output:

• Nếu đồ thị đã cho là một cây, in ra "Yes", ngược lại in ra "No".

Sample Test 1

Input:

3 2
1 2
2 3

Output:

Yes

Sample Test 2

Input:

3 3 
1 2 
2 3 
3 1

Output:

No

Cho một cây ~n~ đỉnh có đỉnh gốc là ~1~. Xác định độ sâu của mỗi đỉnh. Độ sâu của một đỉnh là số lượng cạnh trên đường đi từ đỉnh gốc đến nó.

Input

• Dòng đầu tiên gồm một số nguyên ~n~.
• ~n - 1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u,v~, có một cạnh giữa ~u~ và ~v~.

Output

• In ra ~n~ số nguyên, số nguyên thứ ~i~ là độ sâu của cạnh ~i~.

Điều kiện

• ~1 \le n \le 10^5~.
• ~1 \le u, v \le n~.

Ví dụ

Input:

5
1 2
1 3
3 4
3 5

Output:

0 1 1 2 2

Cho biết cấu trúc của một công ty, nhiệm vụ của bạn là tính số lượng cấp dưới của mỗi người.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ ~(1 \leq n \leq 2 \times 10^{5})~: số lượng nhân viên. Các nhân viên được đánh số ~1, 2, \ldots, n,~ và người có số ~1~ là tổng giám đốc của công ty.
• Sau đó là ~n - 1~ số nguyên: cấp trên trực tiếp trong công ty của mỗi nhân viên ~2, 3, \ldots, n~.

Output

• In ra ~n~ số nguyên: số lượng cấp dưới của mỗi người ~1, 2, \ldots, n~ .

Input

5
1 1 2 3

Output

4 1 1 0 0

Cho một cây vô hướng gồm ~n~ đỉnh, có gốc là đỉnh ~1~. Đỉnh ~i~ gồm một số ~a[i]~, nếu ~a[i] = 1~, nghĩa là có một chú mèo ở đỉnh ~i~, còn ngược lại thì không. Thinkies đang ở đỉnh ~1~, cậu chỉ có thể đi tới các đỉnh khác khi và chỉ khi từ đỉnh ~1~ tới đỉnh đó có số mèo trên các đỉnh liên tiếp nhỏ hơn hoặc bằng ~m~. Hãy đếm số đỉnh lá (các đỉnh không có đỉnh con) mà Thinkies có thể đi vào.

Input:

Dòng đầu gồm ~2~ số nguyên ~n~ và ~m~ (~1 \leq m \leq n \leq 10^5~).

Dòng sau gồm ~n~ số biểu thị dãy ~a~.

~n - 1~ dòng kế tiếp, mỗi dòng gồm 2 số ~u~ và ~v~, biểu thị có cạnh giữa 2 đỉnh ~u~ và ~v~.

Output:

In ra số lá mà Thinkies có thể đi vào

Mẫu:

Input:

4 1
1 1 0 0
1 2
1 3
1 4

Output:

2

Cho một cây có ~n~ đỉnh, hãy xác định số lượng cạnh lớn nhất có thể xóa bỏ để toàn bộ các vùng liên thông còn lại có kích thước chẵn.

Input

• Dòng đầu tiên chứa số nguyên dương ~n \le 10^5~.
• ~n - 1~ dòng tiếp theo chứa 2 số ~u, v (u, v \le n)~ là các cạnh của cây.

Output

• In ra một số nguyên số cạnh có thể xóa
• Nếu không thể có cách cắt thỏa mãn, in ra -1.

Sample Test 1

Input:

4
2 4
4 1
3 1

Output:

1

Sample Test 2

Input:

10
7 1
8 4
8 10
4 7
6 5
9 3
3 5
2 10
2 5

Output:

4

Cho một cây vô hướng không trọng số gồm ~n~ đỉnh.

Với mọi ~1 \le u < v \le n~, gọi ~S(u,v)~ là tập các cạnh nằm trong đường đi ngắn nhất từ ~u~ tới ~v~.

Với mỗi cạnh ~(x,y)~ của cây, hãy đếm xem cạnh đó xuất hiện trong bao nhiêu tập ~S(u,v)~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~x,y~ miêu tả cạnh của cây.

Constraint

• ~1 \le n \le 10^5~

Subtask

• Subtask ~1~ ~(40\%)~: ~n \le 2000~.
• Subtaks ~2~ ~(60\%)~: Không có điều kiện gì thêm.

Output

• In ra kết quả cần tính của mỗi cạnh ~(x,y)~ theo thứ tự Input.

Sample Input 1:

4
1 2
1 3
3 4

Sample Output 1:

3
4
3

Cho một cây vô hướng không trọng số gồm ~n~ đỉnh.

Ban đầu, các cạnh được gán trọng số bằng ~0~.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(a,b)~, tức là sẽ tăng các cạnh trên đường đi ngắn nhất từ đỉnh ~a~ tới đỉnh ~b~ lên ~1~ đơn vị.

Sau ~q~ truy vấn, hãy in ra giá trị của từng cạnh.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~x,y~ miêu tả cạnh của cây.
• Dòng sau gồm số nguyên dương ~q~.
• ~q~ dòng sau, mỗi dòng là hai số nguyên dương ~(a,b)~ miêu tả truy vấn.

Constraint

• ~1 \le n,q \le 10^5~

Subtask

• Subtask ~1~ ~(40\%)~: ~n,q \le 2000~.
• Subtaks ~2~ ~(60\%)~: Không có điều kiện gì thêm.

Output

• In ra kết quả cần tính của mỗi cạnh ~(x,y)~ theo thứ tự Input.

Sample Input 1:

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

Sample Output 1:

1
2
1

Cho một cây vô hướng ~n~ đỉnh. Trên mỗi đỉnh ~i~ sẽ có một trọng số nguyên ~a_i~. Định nghĩa ~g(u,v)~ là giá trị lớn nhất của trọng số các đỉnh trên đường đi ngắn nhất từ ~u~ đến ~v~. Hãy tính tổng ~g(u,v)~ với mọi cặp ~(1 \le u < v \le n)~.

Input:

• Dòng đầu là số nguyên dương ~n~. ~(2 \le n \le 10^5)~.
• Dòng sau gồm n số nguyên ~a_i. (|a_i| <= 10^6)~.
• ~n-1~ dòng sau mỗi dòng gồm 2 số nguyên ~u,v~ miêu tả cạnh nối giữa 2 đỉnh ~u,v~.

Output:

In ra một số nguyên là kết quả của bài toán.

Subtasks

• Subtask 1: ~n \leq 5000~.
• Subtask 2: Không có điều kiện gì thêm.

Sample Test

Input:

3
3 2 4
1 2
1 3

Output:

11

Giải thích:

Ta có : ~g(1,2) + g(1,3) + g(2,3) = 3 + 4 + 4 = 11.~

TR là một hệ thống trao đổi dữ liệu trực tiếp giữa các máy tính đang được thử nghiệm tại trường ~X~. Trường có ~N~ máy tính được đánh số từ ~1~ đến ~N~. Các máy tính đều sử dụng hệ thống TR và được kết nối với nhau theo đồ thị dạng cây.

Ban đầu, hệ thống có một tệp dữ liệu đang được lưu trữ bởi một hoặc hai máy tính. Trường muốn truyền tệp này đến tất cả các máy tính khác trong hệ thống. Cơ chế truyền dữ liệu của hệ thống TR như sau: cứ một phút, mỗi máy tính trong hệ thống chỉ có thể truyền dữ liệu đến duy nhất một máy tính khác được kết nối trực tiếp với nó.

Yêu cầu: Cho số hiệu của các máy tính đang lưu trữ tệp dữ liệu ở thời điểm ban đầu. Hãy tính thời gian tối thiểu để tất cả các máy tính trong hệ thống nhận được tệp dữ liệu.

Dữ liệu vào từ tệp văn bản TDL.INP:

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \lt N \le 10^5)~ là số lượng máy tính;
• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên khác nhau ~x~ và ~y~ ~(1 \le x, y \le N)~ mô tả số hiệu của hai máy tính được kết nối trực tiếp;
• Dòng tiếp theo chứa số ~M~ ~(1\le M\le 2)~ là số lượng máy tính đang lưu trữ tệp dữ liệu ở thời điểm ban đầu;
• Dòng tiếp theo chứa ~M~ số nguyên dương mô tả số hiệu của các máy tính đang lưu trữ tệp dữ liệu ở thời điểm ban đầu;

Dữ liệu ghi ra tệp văn bản TDL.OUT:

Gồm một số nguyên là thời gian tối thiểu hoàn thành công việc.

Ví dụ

Input

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

Output

3

Giải thích

Ban đầu máy ~1~ lưu trữ tệp dữ liệu.

Phút thứ ~1~: máy ~2~ nhận được tệp dữ liệu.

Phút thứ ~2~: máy ~3~ và ~5~ nhận được tệp dữ liệu.

Phút thứ ~3~: máy ~4~ và ~6~ nhận được tệp dữ liệu.

Input

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

Output

2

Giải thích

Ban đầu máy ~1~ và ~2~ lưu trữ tệp dữ liệu.

Phút thứ ~2~: máy ~3~ và ~5~ nhận được tệp dữ liệu.

Phút thứ ~3~: máy ~4~ và ~6~ nhận được tệp dữ liệu.

Minh hoạ

Ràng buộc

• Có ~25\%~ số test ứng với ~25\%~ số điểm có ~N\le 20~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm có ~M=1~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm có ~M=2; N\le 1000~;
• ~25\%~ số test còn lại ứng với ~25\%~ số điểm không có ràng buộc gì thêm.

Một công ty gồm ~N~ người được đánh số từ ~1~ tới ~N~. Tổng giám đốc của công ty được đánh số là ~1~, mỗi người từ ~2~ tới ~N~ có đúng một cấp trên trực tiếp của mình.

Nếu ~i~ là cấp trên trực tiếp của ~j~, ta gọi ~i~ là quản lý của ~j~. Nếu ~i~ là quản lý của ~j~ thì ~i~ cũng là quản lý của những người mà ~j~ quản lý. Không có trường hợp ~i~ là quản lý của ~j~ đồng thời ~j~ là quản lý của ~i~.

Công ty có chế độ lương thưởng rất đặc biệt, người thứ ~i~ có lương là ~a_i~, người cấp dưới có thể có lương cao hơn người quản lý.

Công ty muốn tổ chức một sự kiện cho toàn bộ công ty. Nhưng nếu hai người ~u~ và ~v~ tham gia, trong đó ~u~ là quản lý của ~v~ mà lương của ~u~ không cao hơn lương của ~v~ ~(a_u \le a_v)~ thì sẽ gây ra bất hoà. Công ty muốn chọn ra được nhiều người nhất tham gia sự kiện mà không có sự bất hoà nào.

Phòng tổ chức sự kiện đã lên ~Q~ giả định như sau: Xét người ~u \ (1 \le u \le N)~, chọn ra một số người mà ~u~ là quản lý (có thể chọn hoặc không chọn ~u~) để tham gia sự kiện sao cho:

• Tổng số người được chọn là lớn nhất;
• Không có sự bất hoà nào giữa những người được chọn.

Yêu cầu: Với mỗi giả định, in ra số người nhiều nhất có thể chọn để tham gia sự kiện.

Dữ liệu vào từ file văn bản CONGTY.INP:

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~ ~(1 \le N, Q \le 2 \times 10^5)~;
• Dòng thứ hai gồm ~N~ số nguyên dương, số thứ ~i~ là ~a_i~ mô tả mức lương của người thứ ~i~ ~(1 \le a_i \le 10^9)~;
• Dòng thứ ba gồm ~N - 1~ số nguyên dương, số thứ ~i~ là ~p_i~ mô tả ~p_i~ là cấp trên trực tiếp của ~i+1~ ~(1 \le p_i \le N)~;
• ~Q~ dòng sau, dòng thứ ~i~ gồm một số nguyên dương ~u_i \ (1 \le u_i \le N)~, mô tả giả định thứ ~i~.

Kết quả ghi ra file văn bản CONGTY.OUT:

Với mỗi giả định, in ra kết quả tương ứng.

Ví dụ

Input

6 3
8 4 2 7 1 3
1 1 3 2 3
1
3
4

Output

5
2
1

Giải thích

Hình vẽ minh hoạ như Hình 3.

• Với giả định thứ nhất, chọn các nhân viên: ~1, 2, 5, 4, 6~;
• Với giả định thứ hai, chọn các nhân viên: ~4, 6~;
• Với giả định thứ ba, chọn nhân viên: ~4~.

Input

6 2
7 5 6 4 3 1
1 1 3 3 5
3
1

Output

4
6

Giải thích

• Với giả định thứ nhất, chọn các nhân viên: ~3, 4, 5, 6~;
• Với giả định thứ hai, chọn các nhân viên: ~1, 2, 3, 4, 5, 6~.

Ràng buộc

• Có ~15\%~ số test ứng với ~15\%~ số điểm của bài thoả mãn: ~N \le 15; \ Q = 1~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: nếu ~u~ là quản lý của ~v~ thì ~a_u > a_v~;
• ~15\%~ số test khác ứng với ~15\%~ số điểm của bài thoả mãn: ~i~ là cấp trên trực tiếp của ~i+1~ ~(1 \le i \le N)~;
• ~15\%~ số test khác ứng với ~15\%~ số điểm của bài thoả mãn: ~N \le 1000; \ a_i \le 100~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~N \le 10^5; \ a_i \le 100~;
• ~15\%~ số test còn lại ứng với ~15\%~ số điểm của bài không có ràng buộc gì thêm.

Cho một đồ thị vô hướng có dạng cây, tức là đồ thị gồm ~n~ đỉnh và ~n-1~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~n~, đỉnh thứ ~i~ có trọng số là ~a_i~. Lưu ý dãy ~a~ gồm các phần tử đôi một khác nhau.

Bạn được nhận thêm hai giá trị nguyên không âm ~c~ và ~d~. Xét một đường đi đơn ~P~ trên cây, gọi ~V~ là tập đỉnh trên đường đi này. Chúng ta định nghĩa độ đẹp của ~P~ là: ~ c \times mex_{x \in V} \{a_x\} + d \times max_{x \in V} \{a_x\} ~

Hãy tìm độ đẹp lớn nhất của tất cả các đường đi đơn.

PS: ~mex~ ~V~ là số nguyên không âm nhỏ nhất không xuất hiện trong tập ~V~, ~max~ ~V~ là số lớn nhất trong tập ~V~.

Input:

• Dòng đầu tiên gồm hai ba số nguyên ~n~ ~(1 \le n \le 10^5, 0 \le c,d \le 10^9)~.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~ ~(0 \le a_i \le n-1)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~u_i~ và ~v_i~ miêu tả cạnh ~(u_i,v_i)~ của cây ~(1 \le u_i,v_i \le n)~.

Output:

• In ra đáp án cần tìm.

Subtask:

• Subtask ~1~ (~25\%~ số điểm): ~n \le 200~
• Subtask ~2~ (~25\%~ số điểm): ~n \le 2000~
• Subtask ~3~ (~25\%~ số điểm): ~d = 0~
• Subtask ~4~ (~25\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

25

Cho đồ thị dạng cây ~𝑇[1]~, gồm ~𝑁~ đỉnh, các đỉnh được đánh số từ ~1~ đến ~N~, mỗi đỉnh ~𝑖~ được gán một số nguyên dương ~a_i~, hỏi đường đi có tổng các số ghi trên các đỉnh từ gốc cây xuống một đỉnh bất kì là bao nhiêu?

Input

• Dòng đầu tiên là số ~𝑁~ là số đỉnh của đồ thị.
• Dòng tiếp theo ghi ~𝑁~ số nguyên dương ~𝑎_1, 𝑎_2, … 𝑎_𝑁~ là các số được gán với ~𝑁~ đỉnh theo thứ tự.
• Dòng tiếp theo có ~𝑁~ số ~𝑝_1, 𝑝_2, . . 𝑝_𝑁~ thể hiện có đường đi từ đỉnh ~𝑖~ đến ~𝑝_𝑖~ với ~0 ≤ 𝑝_𝑖 ≤ 𝑁; 𝑝_1 = 0~ vì đỉnh ~1~ là gốc cây ban đầu.

Constraints

• ~N \le 2 \times 10^5, a_i \le 10^9~

Output

• Một số duy nhất là đường đi có tổng lớn nhất.

Ví dụ

Input 1

14
3 2 1 10 1 3 9 1 5 3 4 5 9 8
0 1 1 1 2 2 3 4 4 4 5 5 7 7

Output 1

22

Cho đồ thị dạng cây ~𝑇[1]~ gồm N đỉnh, các đỉnh được đánh số từ ~1~ đến ~N~, mỗi đỉnh ~𝑖~ được gán một số nguyên dương ~𝑎_𝑖~. Ta có thể chọn nhiều đỉnh trên cây, tuy nhiên không được chọn ~2~ đỉnh kề nhau. Hỏi với cách chọn như vậy thì tổng các số lớn nhất có thể nhận được là bao nhiêu?

Input

• Dòng đầu tiên là số ~𝑁~ là số đỉnh của đồ thị.
• Dòng tiếp theo ghi ~𝑁~ số nguyên dương ~𝑎_1, 𝑎_2, … 𝑎_𝑁~ là các số được gán với ~𝑁~ đỉnh theo thứ tự.
• Dòng tiếp theo có ~𝑁~ số ~𝑝_1, 𝑝_2, . . 𝑝_𝑁~ thể hiện có đường đi từ đỉnh ~𝑖~ đến ~𝑝_𝑖~ với ~0 ≤ 𝑝_𝑖 ≤ 𝑁; 𝑝_1 = 0~ vì đỉnh ~1~ là gốc cây ban đầu.

Constraints

• ~N \le 2 \times 10^5, a_i \le 10^9~

Output

• Một số duy nhất là tổng của tập đỉnh lớn nhất.

Subtask

• Có ~30\%~ số test tương ứng với số điểm có ~n \le 20~
• Có ~30\%~ số test khác tương ứng với số điểm có ~p_i = i-1~
• Có ~40\%~ số test còn lại tương ứng với số điểm không có giới hạn gì thêm.

Ví dụ

Input 1

14
3 2 1 10 1 3 9 1 5 3 4 5 9 8
0 1 1 1 2 2 3 4 4 4 5 5 7 7

Output 1

41

Để trang trí căn phòng của mình, T3N quyết định mua về một bức tranh thật đẹp, do là người yêu thiên nhiên nên bức trang T3N chọn có dạng đồ thị cây có ~N~ đỉnh, các đỉnh được đánh số từ ~1~ đến ~N~. Để dán bức tranh lên tường, T3N cần cho keo dán vào các đỉnh của cây, mỗi đỉnh ~𝑖~ mất chi phí ~𝑎_𝑖~.

Để đảm bảo bức tranh hình cây được dán chắc chắn thì mỗi cạnh của cây đều phải được dán ít nhất tại một đầu. Hãy giúp T3N tính chi phí tối thiểu để dán được bức tranh của mình lên tường nhé!

Input

• Dòng đầu tiên là số ~𝑁~ là số đỉnh của đồ thị.
• Dòng tiếp theo ghi ~𝑁~ số nguyên dương ~𝑎_1, 𝑎_2, … 𝑎_𝑁~ là các số được gán với ~𝑁~ đỉnh theo thứ tự.
• Dòng tiếp theo có ~𝑁~ số ~𝑝_1, 𝑝_2, . . 𝑝_𝑁~ thể hiện có đường đi từ đỉnh ~𝑖~ đến ~𝑝_𝑖~ với ~0 ≤ 𝑝_𝑖 ≤ 𝑁; 𝑝_1 = 0~ vì đỉnh ~1~ là gốc cây ban đầu.

Constraints

• ~N \le 2 \times 10^5, a_i \le 10^9~

Output

• Một số duy nhất là chi phí dán tranh nhỏ nhất có thể.

Subtask

• Có ~30\%~ số test tương ứng với số điểm có ~n \le 20~
• Có ~30\%~ số test khác tương ứng với số điểm có ~p_i = i-1~
• Có ~40\%~ số test còn lại tương ứng với số điểm không có giới hạn gì thêm.

Ví dụ

Input 1

14
3 2 1 10 1 3 9 1 5 3 4 5 9 8
0 1 1 1 2 2 3 4 4 4 5 5 7 7

Output 1

23

Nông dân John có một trang trại lớn với ~N~ chuồng ( ~1 \leq N \leq 10^5~ ), một số chuồng đã được sơn và một số chưa được sơn. Nông dân John muốn sơn những chuồng còn lại để tất cả các chuồng đều được sơn, nhưng ông chỉ có ba màu sơn có sẵn. Hơn nữa, con bò quý Bessie của ông sẽ bị nhầm lẫn nếu hai chuồng có thể trực tiếp đi đến nhau có cùng màu, vì vậy ông muốn đảm bảo rằng tình huống này không xảy ra.

Đề bài đảm bảo rằng các kết nối giữa ~N~ chuồng không tạo thành bất kỳ 'chu trình' nào. Điều này có nghĩa là giữa bất kỳ hai chuồng nào, chỉ có nhiều nhất một dãy kết nối sẽ dẫn từ chuồng này đến chuồng kia.

Có bao nhiêu cách để Nông dân John sơn các chuồng còn lại mà chưa được sơn?

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ( ~0 \leq K \leq N~ ), lần lượt là số lượng chuồng trong trang trại và số lượng chuồng đã được sơn.
• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x~ và ~y~ ( ~1 \leq x, y \leq N, x \ne y~ ) mô tả một con đường kết nối trực tiếp chuồng ~x~ và chuồng ~y~.
• ~K~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~b~ và ~c~ ( ~1 \leq b \leq N, 1 \leq c \leq 3~ ) cho biết chuồng ~b~ đã được sơn màu ~c~.

Output

• Tính số cách hợp lệ để sơn các chuồng còn lại, theo modulo ~10^9+7~, sao cho không có hai chuồng nào được kết nối trực tiếp có cùng màu.

Constraints

• ~3 \leq N \leq 99999~, ~N~ lẻ
• ~1 \leq C \leq N~
• ~1 \leq E_{i} \leq N~
• ~2 \leq B_{1i}, B_{2i} \leq N~

Input

4 1
1 2
1 3
1 4
4 3

Output

8

Bạn vừa được HCV IOI nên thầy Tùng quyết định thưởng cho bạn. Thầy cho bạn một cây có ~n~ đỉnh. Với mỗi đỉnh ~i~ cho 2 số ~l_i \le r_i~. Việc bạn cần làm là chọn một số ~v_i~ ở mỗi đỉnh sao cho ~l_i \le v_i \le r_i~ và số tiền được thưởng (tính bằng triệu VND) sẽ là tổng của ~|v_i - v_j|~ với toàn bộ các cạnh ~(i, j)~ vô hướng của cây. Hãy in ra số tiền nhiều nhất bạn có thể được thầy thưởng.

Input

• Dòng đầu tiên là số nguyên dương ~n \le 10 ^ 5~ là số đỉnh của cây.
• ~n~ dòng tiếp theo mỗi dòng ~i~ gồm 2 số ~l_i \le r_i \le 10^9~ là chỉ số của đỉnh thứ ~i~.
• ~n - 1~ dòng tiếp theo mỗi dòng là 2 số ~u, v~ là cạnh của cây.

Output

• In ra một số là số tiền lớn nhất bạn có thể được thưởng.

Subtasks

• Subtask 1: ~n \leq 20~.
• Subtask 2: Với mỗi ~i < n~, tồn tại một cạnh ~i~ với ~i + 1~.
• Subtask 3: Không có điều kiện gì thêm.

Sample Test

Input:

3
1 3
4 6
7 9
1 2
2 3

Output:

8

Tèo cảm thấy bài toán mà Tí giải ở trên quá đơn giản nên thách đố thêm bài toán sau. Thay vì đặt các viên ngọc trên đường thẳng, Tèo đặt chúng lên một cái cây (đồ thị liên thông vô hướng và không có chu trình). Để đơn giản, Tèo chỉ chọn ra các viên ngọc thuộc một trong 4 màu: đỏ, xanh, lục, vàng.

Tèo muốn chia nhỏ cây thành các thành phần liên thông bằng cách bỏ đi vài cạnh. Đồng thời Tèo không muốn thấy thành phần liên thông nào chứa ba màu đỏ, xanh, lục cùng lúc (vì theo Tèo, chúng làm mất vẻ đẹp của nhau). Nhiệm vụ của Tí là đếm xem có bao nhiêu bỏ đi một vài cạnh của cây (có thể không bỏ cạnh nào) sao cho trong các thành phần liên thông còn lại, không có thành phần liên thông nào chứa cả 3 màu đỏ, xanh, lục.

Hai cách chia được xem là khác nhau nếu có một cạnh bị bỏ trong cách chia này mà không bị bỏ trong cách chia còn lại.

Yêu cầu: In ra số cách chia sau khi ~\mod 10^9+7~

Input

• Dòng đầu tiên là số tự nhiên ~n\ (n\leq 3\cdot 10^5)~ chỉ số viên ngọc.
• Dòng thứ hai chứa một xâu miêu tả màu các viên ngọc. Chữ cái thứ ~i~ trong xâu tương ứng với màu của viên ngọc thứ ~i~ (D: Đỏ, X: Xanh, L: Lục, V: Vàng)
• ~n-1~ dòng tiếp theo chứa hai số nguyên ~u,v~ (~1 ≤ u,v ≤ n~) miêu tả một cạnh nối viên ngọc thứ ~u~ và thứ ~v~.
• Dữ liệu đảm bảo đồ thị là một cây.

Output

• Ghi ra một số nguyên duy nhất - số cách chia.

Scoring

• Subtask ~1~ (~30\%~ số điểm): Cây là đường thẳng, các cạnh trên cây có dạng (~i,i+1~) với (~0<i<n~) .</li>
• Subtask ~2~ (~30\%~ số điểm): Không có đỉnh nào màu đỏ.
• Subtask ~3~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

 4
DXLV
1 2
2 3
3 4 

Sample Output 1

6

Explanation 1

• Các cách chia thỏa mãn là: ~(12)|(34), (1)|(234), (1)|(23)|(4), (1)|(2)|(3)|(4), (1)|(2)|(34), (12)|(3)|(4)~. Lưu ý các viên ngọc ~1, 2, 3~ không được xuất hiện trong cùng một thành phần liên thông.

Cho một cây có trọng số gồm ~n~ đỉnh, được đánh số từ ~1~ đến ~n~. Dễ thấy là với mỗi cặp đỉnh ~(u,v)~ ta luôn có duy nhất một đường đi đơn từ đỉnh ~u~ đến ~v~.

Hãy đếm xem trong ~n^2~ cặp đỉnh ~(u,v)~, có bao nhiêu cặp đỉnh mà trọng số trên đường đi từ ~u~ đến ~v~ tạo thành một dãy tăng chặt?

Input

• Dòng đầu chứa hai số nguyên ~n~ ~(n \le 2 \times 10^5)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u, v, w~ ~(1≤u,v≤n; u \neq v ; 0≤w≤10^9)~ mô tả một cạnh của cây nối hai đỉnh ~u~ và ~v~ với trọng số ~w~.

Output

• In ra một số nguyên duy nhất là số cặp cần tìm.

Sample Input 1

3
1 2 3
2 3 8

Sample Output 1

5

Sample Input 2

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

Sample Output 2

9

Cho một cây có trọng số gồm ~n~ đỉnh, được đánh số từ ~1~ đến ~n~, trọng số của đỉnh thứ ~i~ là ~a_i~. Gọi ~S(i)~ là dãy các trọng số của các đỉnh trên đường đi từ ~1~ tới ~i~.

Với mỗi ~i~, hãy tìm độ dài dãy con tăng dài nhất của ~S(i)~.

Input

• Dòng đầu chứa số nguyên ~n~ ~(n \le 2 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ miêu tả trọng số của các đỉnh ~(1 \le a_i \le 10^9)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1≤u,v≤n; u≠v)~ mô tả một cạnh của cây nối hai đỉnh ~u~ và ~v~.

Output

• In ra ~n~ số nguyên là độ dài của dãy con tăng dài nhất của ~S(i)~.

Subtask

• Subtask ~1~: ~a_i \le 100~. ~(30\%)~
• Subtask ~2~: Không có đỉnh nào có quá hai cạnh nối. ~(30\%)~
• Subtask ~3~: Không có ràng buộc gì thêm. ~(40\%)~

Sample Input 1

10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10

Sample Output 1

1
2
3
3
4
4
5
2
2
3