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

Liyue là một bến cảng giàu có bậc nhất nằm phía đông đại lục Teyvat. Vùng đất màu mỡ được tạo nên từ những dãy núi cao, rừng đá sừng sững, đồng bằng rộng lớn và những bờ sông nhộn nhịp sức sống, nơi đây rực rỡ sắc màu trong bốn mùa. Là quốc gia được bảo hộ bởi Thần Khế Ước, những hợp đồng và giao kèo luôn được đặt ưu tiên hàng đầu trong các giao dịch giữa các cá nhân hay cơ sở kinh doanh nơi đây.

Ở Liyue có ~n~ cơ sở kinh doanh đánh số từ ~1~ tới ~n~, cơ sở thứ ~i~ có tọa độ ở ~(x_i,y_i)~ và giữa các cơ sở kinh doanh này có ~n-1~ liên kết trực tiếp giữa các cặp cơ sở kinh doanh nào đó với nhau. Giữa hai cơ sở ~s~ và ~t~ bất kì đều tồn tại ít nhất một danh sách các cơ sở ~s = a_1,a_2,...,a_k = t~ sao cho tồn tại liên kết trực tiếp giữa ~a_i~ và ~a_{i+1}~ với mọi ~1 \le i \le k~.

Khi cơ sở kinh doanh ~a~ muốn hợp tác kinh doanh với cơ sở ~b~, họ sẽ cần phải hợp tác với ~k~ cơ sở phân biệt ~t_1,t_2,...,t_k~ khác sao cho ~a~ có có liên kết trực tiếp với ~t_1~, ~t_1~ có liên kết trực tiếp với ~t_2~, ... , ~t_k~ có liên kết trực tiếp với ~b~. . Nếu ~a~ và ~b~ đã có liên kết trực tiếp thì có thể không cần hợp tác thêm với cơ sở nào khác. Để ký kết hợp đồng hợp tác giữa ~k+2~ cơ sở nêu trên, người ta sẽ cần phải tổ chức một cuộc gặp mặt ở một tọa độ ~S(x_S,y_S)~ nào đó làm điểm gặp mặt. Khi đó chi phí di chuyển sẽ là tổng khoảng cách Manhattan giữa ~S~ và trụ sở của ~k+2~ cơ sở nêu trên. Trong tất cả các phương án chọn ra ~k~ cở sở và tọa độ , hãy cho biết chi phí di chuyển nhỏ nhất là bao nhiêu.

Khoảng cách Manhattan giữa điểm ~(x,y)~ và ~(u,v)~ là ~|x-u| + |y-v|~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(n,q \le 5 \times 10^4)~ lần lượt là số cơ sở kinh doanh và số câu hỏi.
• Dòng tiếp chứa ~n~ số nguyên ~x_1,x_2,...,x_n~ ~(1 \le x_i \le 10^9)~ là tọa độ ~x~ của các cơ sở kinh doanh.
• Dòng tiếp chứa ~n~ số nguyên ~y_1,y_2,...,y_n~ ~(1 \le x_i \le 10^9)~ là tọa độ ~y~ của các cơ sở kinh doanh.
• Trong ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i \neq v_i~ ~(1 \le u_i,v_i \le n)~ thể hiện rằng giữa ~u_i~ và ~v_i~ có liên kết trực tiếp.
• Trong ~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i \neq b_i~ ~(1 \le a_i,b_i \le n)~ là câu hỏ thứ ~i~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ chứa một số nguyên duy nhất là chi phí di chuyển nhỏ nhất cho câu hỏi thứ ~i~.

Ràng buộc

• Có ~20\%~ số test thỏa mãn: ~n,q \le 100~
• Có ~20\%~ số test thỏa mãn: ~x_i,y_i \le 10, u_i = i, v_i = i+1~
• Có ~20\%~ số test thỏa mãn: ~u_i = i, v_i = i+1~
• Có ~20\%~ số test thỏa mãn: ~x_i,y_i \le 10~
• Có ~20\%~ số test thỏa mãn: Không có ràng buộc gì thêm.

  Ví dụ

Input 1

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

Output 1

4
6
8
5