📘 Câu chuyện

Trên cành cây cổ thụ có n chiếc lá được nối với nhau bởi các cành cây, tạo thành một mạng lưới không có chu trình – chính là một cái cây. Mỗi chiếc lá có thể được tô màu đen hoặc để trắng. Nhưng có một quy tắc kỳ lạ: nếu một chiếc lá được tô đen, thì tất cả những chiếc lá kề với nó (có nối trực tiếp bằng cành) phải để trắng. Bọn trẻ tinh nghịch muốn tô màu thật nhiều chiếc lá thành đen mà vẫn tuân theo quy tắc trên. Bạn hãy giúp chúng tô màu để số lượng lá đen là nhiều nhất có thể.

📥 Input

• Dòng đầu tiên chứa số nguyên n.
• n - 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v mô tả cạnh nối giữa u và v.

📤 Output

In ra một số nguyên duy nhất - số lượng đỉnh lớn nhất có thể tô màu đen.

Điều kiện

• 1 ≤ n ≤ 10⁵.
• 1 ≤ u, v ≤ n.

🧪 Ví dụ

Input:

5
1 2
2 3
1 4
4 5

Output:

3

📘 Câu chuyện

Trên rừng rậm cổ xưa có n cây cổ thụ, mỗi cây có thể được sơn bằng một trong ba màu đỏ, xanh lá hoặc vàng. Nhưng nếu hai cây nào kề nhau mà có cùng màu, điều đó sẽ gây ra sự mất cân bằng sinh thái! Hội bảo vệ rừng yêu cầu: hãy đếm số cách tô màu các cây sao cho không có hai cây kề nhau có màu giống nhau.

📥 Input

• Dòng đầu tiên là số nguyên n: số lượng cây.
• n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u và v, biểu diễn một con đường nối giữa hai cây u và v.

📤 Output

In ra số cách tô màu khác nhau thoả yêu cầu, modulo 10^9 + 7.

🔒 Ràng buộc

• 1 ≤ n ≤ 10^5
• 1 ≤ u, v ≤ n

🧪 Ví dụ

Input:

5
1 2
1 3
2 4
2 5

Output:

48

📘 Mô tả

Cho một cây gồm n đỉnh, đỉnh i mang giá trị Ai. Hãy tìm một đường đi đơn sao cho tổng các giá trị trên các đỉnh thuộc đường đi đó là lớn nhất.

📥 Input

• Dòng đầu tiên chứa số nguyên n.
• Dòng thứ hai chứa n số nguyên Ai.
• n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v — có cạnh nối u và v.

📤 Output

In ra một số nguyên duy nhất — tổng lớn nhất tìm được.

📜 Điều kiện

• 1 ≤ n ≤ 105.
• |Ai| ≤ 109.

🧪 Ví dụ

Input:

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

Output:

7

📘 Mô tả

Cho một cây gồm n đỉnh đánh số từ 1 đến n. Một đường đi đơn là dãy đỉnh liên tiếp sao cho mỗi cặp đỉnh kề nhau được nối bởi một cạnh và không đỉnh nào lặp lại. Hãy đếm số lượng đường đi đơn có chính xác k cạnh.

📥 Input

• Dòng đầu chứa hai số nguyên n và k.
• n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u và v mô tả cạnh nối u với v.

📤 Output

In ra một số nguyên duy nhất là số đường đi thoả mãn.

🔒 Ràng buộc

• 1 ≤ n ≤ 105
• 1 ≤ k ≤ 100
• 1 ≤ u, v ≤ n

🧪 Ví dụ

Input:

5 2
1 2
2 3
1 4
4 5

Output:

3

📎 Ghi chú

• Có ba đường đi độ dài 2: 1 → 2 → 3, 2 → 1 → 4, 1 → 4 → 5.

📘 Mô tả

Cho một cây gồm n đỉnh đánh số từ 1 đến n. Một đồ thị con là một tập đỉnh liên thông và không rỗng. Hãy đếm số lượng đồ thị con của cây, kết quả lấy modulo 109 + 7.

📥 Input

• Dòng đầu chứa số nguyên n.
• n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v mô tả cạnh nối u với v.

📤 Output

In ra một số nguyên duy nhất là số đồ thị con, modulo 109 + 7.

🔒 Ràng buộc

• 1 ≤ n ≤ 105
• 1 ≤ u,v ≤ n

🧪 Ví dụ

Input:

5
1 2
1 3
3 4
3 5

Output:

17

📘 Mô tả

Cho một cây có n đỉnh đánh số từ 1 đến n. Với mỗi đỉnh i bạn được chọn một giá trị nguyên ai sao cho li ≤ ai ≤ ri. Độ đẹp của cây được định nghĩa là tổng |au - av| trên mọi cạnh (u, v). Hãy tìm giá trị độ đẹp lớn nhất có thể.

📥 Input

• Dòng đầu chứa số nguyên n.
• n dòng tiếp theo, mỗi dòng gồm hai số nguyên li, ri.
• n - 1 dòng cuối, mỗi dòng gồm hai số nguyên u, v mô tả cạnh nối u với v.

📤 Output

In ra giá trị độ đẹp lớn nhất của cây.

🔒 Ràng buộc

• 1 ≤ n ≤ 105
• 1 ≤ li ≤ ri ≤ 109
• 1 ≤ u, v ≤ n

🧪 Ví dụ

Input:

3
1 3
4 6
7 9
1 2
2 3

Output:

8

📘 Mô tả

Công ty được mô hình hoá thành một cây có n nhân viên, gốc là giám đốc 1. Với mỗi nhân viên i (2 ≤ i ≤ n) biết trước người quản lí trực tiếp pi. Công ty nhận một dự án mới: nếu nhân viên i chi j tiền (0 ≤ j ≤ L) thì danh tiếng của công ty tăng Ai,j. Nhân viên i yêu cầu tổng chi phí của chính họ và toàn bộ cấp dưới không vượt quá Si. Hãy tìm mức tăng danh tiếng lớn nhất có thể đạt được.

📥 Input

• Dòng đầu chứa hai số nguyên n, L.
• Dòng thứ hai chứa n - 1 số nguyên pi (2 ≤ i ≤ n).
• Dòng thứ ba chứa n số nguyên Si.
• n dòng tiếp theo, dòng thứ i (tính từ 1) chứa L + 1 số nguyên Ai,0, …, Ai,L.

📤 Output

In ra một số nguyên là mức danh tiếng lớn nhất công ty có thể đạt.

🔒 Ràng buộc

• 1 ≤ n, L ≤ 500
• 1 ≤ pi ≤ n
• 0 ≤ Si ≤ L
• 0 ≤ Ai,j ≤ 106

🧪 Ví dụ

Input:

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

Output:

11