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 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 có ~n~ nút được đánh số từ ~1~ đến ~n~.

Một matching là tập hợp các cạnh trên đồ thị không có chung đỉnh. Hãy tìm một matching có số lượng cạnh nhiều nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~, với ~1 \le n \le 2 \cdot 10^5~.
• ~n-1~ dòng, mỗi dòng chứa 2 số nguyên dương ~a~ và ~b~, với ~1 \le a, b \le n~, thể hiện có cạnh nối giữa nút ~a~ và nút ~b~.

Output

• Số lượng cạnh của matching lớn nhất.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

2

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

Ivan Tèo rất thích thịt vịt, một hôm cậu tới thăm đất nước DuckLand, gồm ~n~ thành phố được nối với nhau bằng ~n-1~ con đường hai chiều, đảm bảo rằng ~n~ thành phố thông thương với nhau. Con đường thứ ~i~ nối hai thành phố ~u_i,v_i~ với nhau và gồm ~c_i~ con vịt.

Giả sử Tèo xuất phát từ thành phố ~s~, cậu sẽ đi tới một thành phố khác sao cho không con đường nào được đi qua nhiều hơn ~1~ lần, và mua hết các con vịt trên đường đi đó.

Tèo muốn biết nếu cậu xuất phát từ thành phố ~s~ với ~s~ lần lượt tương ứng ~1,2,3,...,n~, cậu sẽ mua được tối đa bao nhiêu con vịt nếu đi tối ưu?

Input

• Dòng đầu là số nguyên ~n~ ~(1 \le n \le 10^5)~
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên dương ~u_i,v_i,c_i~ xác định một con đường hai chiều giữa thành phố ~u_i,v_i~ với độ dài ~c_i~. ~(u_i,v_i \le n, c_i \le 10^4)~

Subtask

• Subtask ~1~ ~(50\%)~ : ~K \le N \le 10^3~
• Subtask ~2~ ~(50\%)~ : Không ràng buộc gì thêm.

Output

• Gồm ~n~ số nguyên dương trên một dòng, số thứ ~i~ là số con vịt tối đa Tèo có thể mua nếu đi từ thành phố ~s = i~.

Sample Input 1

4
1 2 4
2 3 5
3 4 7

Sample Output 1

16 12 9 16

Công ty ABC có ~𝑁~ người. Ngoài giám đốc, mỗi người có duy nhất một cấp trên trực tiếp quản lý. Người ~𝑋~ được gọi là sếp của người ~Y~ nếu ~𝑋~ là cấp trên trực tiếp của ~𝑌~ hoặc ~𝑋~ là sếp của cấp trên trực tiếp của ~𝑌~. Để quảng cáo cho tình hình hoạt động, cũng như điều kiện làm việc tốt của công ty, Giám đốc muốn đưa ra ~𝐾~ người có tổng tiền lương lớn nhất sao cho không có hai người nào trong ~𝐾~ người đó mà người này là sếp người kia.

Yêu cầu: Tính tổng tiền lương lớn nhất của những người đã chọn.

Input

• Dòng đầu là số nguyên ~𝑇 ≤ 100~ - số lượng test trong file dữ liệu. Theo sau là 𝑇 nhóm dòng, mỗi nhóm dòng chứa:
• Dòng đầu chứa hai số nguyên dương 𝑁,𝐾
• Dòng thứ ~𝑖 (1 ≤ 𝑖 ≤ 𝑁)~ trong ~𝑁~ dòng tiếp theo chứa hai số tự nhiên ~𝑝_𝑖, 𝑤_𝑖~ ~(𝑤𝑖 ≤10^3; 𝑝_𝑖 ≤ 𝑁, )~. Với ~𝑝_𝑖~ là cấp trên trực tiếp của người thứ ~𝑖~ (~𝑝_𝑖 = 0~ khi người ~𝑖~ là giám đốc công ty), ~𝑤_𝑖~ là tiền lương người ~𝑖~ nhận được.

Tổng số dòng trong input không vượt quá ~10^5+2~

Subtask

• Subtask ~1~ ~(50\%)~ : ~K \le N \le 10~
• Subtask ~2~ ~(25\%)~ : ~K \le 10, N \le 10^4, T \le 10~
• Subtask ~3~ ~(25\%)~ : ~K \le 10^3, N \le 10^5~

Constraints

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

Output

• ~𝑇~ dòng tương ứng ước lượng giá trị lớn nhất tiền lương trong ~𝑇~ test theo thứ tự. Nếu không thể chọn đủ ~𝐾~ người thỏa mãn thì đưa ra ~0~.

Sample Input 1

1
6 3
0 9
1 5
2 6
6 1
2 3
1 2

Sample Output 1

11

Thành phố HNAms có ~𝑛~ ngôi làng. Các ngôi làng được kết nối với nhau bởi ~𝑛 - 1~ con đường mòn. Con đường giữa hai làng ~𝑢_𝑖~ 𝑣à ~𝑣_𝑖~ có độ dài ~𝑤_𝑖~ ~(𝑘𝑚)~. Vào vụ thu hoạch, ngôi làng thứ ~𝑖~ thu hoạch dư ~𝑝_𝑖~ tấn lương thực. Để tích trữ cho năm sau, lãnh đạo thành phố muốn muốn xây dựng một kho lương thực đảm bảo an toàn và không bị mối mọt. Sau đó, thu mua hết tất cả lương thực dôi dư của bà con vận chuyển về kho đó. Kho cần được đặt tại một trong các ngôi làng của thành phố. Chi phí để vận chuyển một tấn lương thực đi trên đoạn đường ~1~ 𝑘𝑚 là là ~1~ đồng. Duck là người chuẩn bị tham gia đấu thầu cung cấp dịch vụ vận tải vận chuyển lương thực. Duck muốn biết rằng trong trường hợp tốt nhất và tệ nhất, chi phí vận chuyển mà Duck phải bỏ ra là bao nhiêu?

Input

• Dòng đầu chứa số nguyên dương ~𝑛~ ~(𝑛 ≤ 10^5)~ – số ngôi làng.
• ~n - 1~ dòng tiếp, dòng thứ ~𝑖~ chứa ~3~ số nguyên dương ~𝑢_𝑖, 𝑣_𝑖, 𝑤_𝑖~ xác định con đường thứ ~𝑖~ ~(𝑢_𝑖 , 𝑣_𝑖 ≤ 𝑛; 𝑤_𝑖 ≤ 10^4)~
• Dòng cuối cùng chứa ~𝑛~ số nguyên ~𝑝_1, 𝑝_2, … , 𝑝_𝑛 (𝑝_𝑖 ≤ 10^4)~ là lượng lương thực dôi dư của từng làng theo thứ tự

Subtask

• Subtask ~1~ ~(30\%)~ : ~n \le 100~
• Subtask ~2~ ~(20\%)~ : ~n \le 1000~
• Subtask ~3~ ~(50\%)~: Không giới hạn gì thêm

Output

• In ra chi phí tối thiểu và tối đa mà Duck cần chuẩn bị trong trường hợp tốt nhất và xấu nhất

Sample Input 1

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

Sample Output 1

25 51

Đấ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):