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

Mai Sakurajima thay vì theo nghiệp diễn xuất giờ đã đi làm trong một công ty lớn. Trớ trêu thay, công ty ấy đang có một cuộc cắt giảm nhân sự. Công ty của cô có ~n~ người, đánh số từ 1 đến ~n~. Giám đốc có cấp cao nhất, số thứ tự là 1. Mô hình tổ chức của công ty như sau: mỗi nhân viên có duy nhất một cấp trên tực tiếp. Giám đốc có một danh sách ghi lại cấp trên trực tiếp của mỗi nhân viên từ 2 đến ~n~ (nhân viên thứ 1 chính là giám đốc).

Công ty muốn cắt giảm nhân viên theo quy tắc sau: Nếu một nhân viên bất kì bị cắt giảm thì tất cả các nhân viên cấp dưới của nhân viên đó cũng bị cắt giảm. Giám đốc sẽ không bị cắt giảm. Có thể không có nhân viên nào bị cắt giảm. Nói cách khác, nếu coi công ty là một cái cây gốc 1, khi cắt đỉnh ~i~, mọi đỉnh trong cây con gốc ~i~ cũng sẽ bị cắt.

Vì rất lo lắng cho công việc của mình, hãy giúp Mai xác định số lượng phương án cắt giảm nhân viên khác nhau của công ty thỏa mãn điều kiện trên, vì số lượng có thể rất lớn nên hãy in ra phần dư của kết quả cho ~10^9+7~.

Input:

• Dòng đầu chứa số nguyên dương n. (~1 \le n \le 10^5~).
• Từ dòng thứ 2 đến dòng thứ ~n~, mỗi dòng in ra một số là cấp trên trực tiếp của nhân viên thứ ~i~.

Output:

• In ra số nguyên duy nhất là phần dư của số lượng phương án cắt giảm nhân viên khác nhau của công ty cho ~10^9+7~. Hai phương án khác nhau khi tập nhân viên còn lại khác nhau.

Sample Test

Input:

4
1
1
3

Output:

6

Giải thích:

Có 6 phương án để cắt giảm nhân viên như sau:

• Không cắt giảm nhân viên nào.
• Cắt giảm nhân viên 2.
• Cắt giảm nhân viên 3
• Cắt giảm nhân viên 4.
• Cắt giảm nhân viên 2,3.
• Cắt giảm nhân viên 2,4.

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~, 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

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 gồm ~n~ đỉnh với các trọng số trên cạnh.

Bạn có ~q~ truy vấn có dạng như sau:

• Nhân thử các cạnh nối với đỉnh ~u_i~ lên ~x_i~ lần, hỏi đường kính của cây mới có độ dài là bao nhiêu.
• Lưu ý là ta chỉ nhân thử, sau truy vấn này thì cây về nguyên bản.

Input

• Dòng đầu 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 ~u~, ~v~ và ~w~ miêu tả cạnh ~(u,v)~ có độ dài ~w~ của cây.
• Dòng tiếp theo gồm số nguyên dương ~q~.
• ~q~ dòng sau, mỗi dòng gồm hai số nguyên dương ~u_i,y_i~ miêu tả truy vấn.

Output

• Với mỗi truy vấn, in ra độ dài đường kính của cây mới trong giả định.

Constraints

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

Subtask

• ~30\%~ số điểm thỏa mãn ~n \le 2000~.
• ~30\%~ số điểm thỏa mãn cây là đường thẳng.
• ~40\%~ số điểm thỏa mãn ~n \le 10^5~

Sample Input 1

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

Sample Output 1

11
18
27

Đất nước ~HNAms~ đã và đang được xây dựng bởi thị trưởng Mrtee. Đất nước ban đầu có ~n~ thành phố được đánh số từ ~1~ tới ~n~, thành phố thứ ~i~ có dân số là ~w_i~. Tất nhiên đất nước thì phải có đường cao tốc, và có ~n-1~ tuyến đường đang được hốc trưởng Kh0i dự kiến xây dựng, tuyến đường thì ~i~ nối giữa hai thành phố ~u_i~ và ~v_i~ với chi phí là ~c_i~. Dù là hốc trưởng nhưng Kh0i vẫn đủ tỉnh táo để thiết kế ~n-1~ con đường này nếu được xây dựng hết thì toàn bộ ~n~ thành phố sẽ được kết nối với nhau.

Tiến hành xây dựng, Mrtee giao cho Kh0i ~k~ ngày, ngày thứ ~i~ cậu sẽ phải làm một công việc như sau:

• Chọn một thành phố ~c_i~, sau đó chọn ~2~ con đường chưa được xây thỏa mãn nó nối thành phố ~c_i~ với một thành phố nào đó.

Sau ~k~ ngày, độ hiệu quả của việc xây dựng được Mrtee đánh giá như sau:

• Gọi ~P~ là tổng dân số của các thành phố ~c~ được chọn ít nhất một lần.
• Gọi ~S~ là tổng chi phí để xây dựng các tuyến đường trong ~k~ ngày vừa qua.
• Độ hiệu quả chính là ~P - S~.

Tất nhiên Kh0i muốn công trình của mình có độ hiệu quả lớn nhất, nhưng đen đủi là cậu lại không học trường xây dựng, vậy nên các bạn hay giúp Kh0i nhé!

Input

• Dòng đầu là hai số nguyên ~n,k~ ~(1 \le n \le 2 \times 10^5, 2\times k \le n)~.
• Dòng thứ hai gồm ~n~ số nguyên ~w_1,w_2,...,w_n~ ~(w_i \le 10^8)~
• ~n-1~ dòng sau, mỗi dòng gồm ~2~ số nguyên ~u_i,v_i~ và ~c_i~, miêu tả con đường thứ ~i~.
• Dữ liệu đảm bảo rằng luôn có cách để xây ~k~ con đường thỏa mãn.

Subtask

• Subtask ~1~ ~(25\%)~ : ~1 \le n \le 200~
• Subtask ~2~ ~(25\%)~ : ~1 \le n \le 1500~
• Subtask ~3~ ~(25\%)~ : ~u_i = i, v_i = i+1~
• Subtask ~4~ ~(25\%)~ : Không giới hạn gì thêm.

Output

• In ra độ hiệu quả tối đa của công trình.

Sample Input 1

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

Sample Output 1

-3

Explanation 1

Ta thực hiện như sau (các con đường cùng màu là các con đường được chọn cùng đỉnh):

Sample Input 1

8 3 
4 5 1 2 3 1 3 5
4 8 1
3 7 7
2 1 15
7 8 1
6 7 5
8 5 2
7 1 5

Sample Output 1

-13

Explanation 1

Ta thực hiện như sau (các con đường cùng màu là các con đường được chọn cùng đỉnh):