Cho một cây ~n~ đỉnh gốc ở ~1~.

Marisa có kế hoạch chạy bộ trong ~k~ ngày. Mỗi ngày, cô sẽ chọn một địa điểm khác nhau và bắt đầu chạy từ ~1~.

Khoảng cách từ ~u~ đến ~v~ là số cạnh trên đường đi ngắn nhất từ ~u~ đến ~v~.

Để việc tập thể dục phát huy hiệu quả tối đa, cô muốn khoảng cách chạy trong ~k~ ngày phải là tối đa.

Input

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

Output

• In ra một số nguyên là khoảng cách tối đa.

Điều kiện

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

  Ví dụ

Input:

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

Output:

7

Chú ý: Marisa có thể chọn các đỉnh ~4, 5, 6~. Khoảng cách tới ~1~ lần lượt là ~2, 2, 3~.

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

Hãy tìm đường đi dài nhất ở trên cây, biết rằng độ dài đường đi từ ~u~ tới ~v~ chính bằng số cạnh trên đường đi đơn từ ~u~ tới ~v~.

Input

• Dòng đầu chứa hai số nguyên ~n~ ~(1 \le n \le 10^5)~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ miêu tả cạnh của cây.

Output

• Đưa ra khoảng cách xa nhất của hai đỉnh bất kì trên cây.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

3

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

Định nghĩa "bán kính của một đỉnh" hay ~R(u)~ là số cạnh ít nhất cần dùng để đỉnh này có thể tới thăm bất kì đỉnh nào trên cây.

Hãy tìm ~R(u)~ nhỏ nhất, nếu có nhiều đỉnh ~u~ thỏa mãn, in ra tất cả các đỉnh đó theo thứ tự từ bé tới lớn.

Input

• Dòng đầu chứa hai số nguyên ~n~ ~(1 \le n \le 10^5)~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ miêu tả cạnh của cây.

Output

• Dòng đầu tiên gồm hai số nguyên dương ~r~ và ~k~ lần lượt là bán kính nhỏ nhất và số đỉnh thỏa mãn.
• Dòng thứ hai gồm ~k~ số nguyên dương là các đỉnh thỏa mãn theo thứ tự tăng dần.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

2 2
1 3

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

Cho cây gồm ~n~ đỉnh, đỉnh thứ ~i~ có trọng số là ~s_i~.

Hãy tìm một đường đi sao cho tổng trọng số các đỉnh trên cây là lớn nhất.

Input

• Dòng đầu chứa hai số nguyên ~n~ ~(n \le 10^5)~.
• Dòng thứ hai gồm ~n~ số, số thứ ~i~ là ~s_i~ tương đương với trọng số của đỉnh thứ ~i~ ~(|s_i| \le 10^9)~.

• ~n-1~ dòng sau, mỗi dòng sau gồm hai số ~u,v~ miêu tả cạnh ~(u,v)~ của cây,

  Output

• Gồm một dòng chứa một số là tổng trọng số lớn nhất tìm được.

Sample Input 1

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

Sample Output 1

6

Để 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.

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

Cho một cây gồm ~n~ đỉnh.

Nhiệm vụ của bạn là với mỗi nút, hãy tìm tổng khoảng cách từ nó tới tất cả các nút khác.

Input

• Dòng đầu chứa một số nguyên ~n:~ số lượng nút. Các nút được đánh số ~1,2,... ,n~.
• Sau đó là ~n-1~ dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên ~a~ và ~b~: có một cạnh nối nút ~a~ và ~b~.

Output

• In ra ~n~ số nguyên~:~ tổng khoảng cách từ các nút ~1,2,3,\dots,n~.

Constraints

• ~1 ≤ n ≤ 2⋅10^5~
• ~1 ≤ a,b ≤ n~

Example

Sample Input

5
1 2
1 3
3 4
3 5

Sample Output

6 9 5 8 8

Note

Trong Test ví dụ:

Với nút ~1~

• Khoảng cách từ nút ~1~ tới:
  • nút ~2~ là ~1~,
  • từ nút ~1~ tới nút ~3~ là ~1~,
  • từ nút ~1~ tới nút ~4~ là ~2~,
  • từ nút ~1~ tới nút ~5~ là ~2~

~\Rightarrow~ Tổng khoảng cách từ nút ~1~ tới các nút còn lại là ~1 + 1 + 2 + 2 = 6~, vậy nên ta in ra ~6~.

Tương tự với các đỉnh còn lại