Bài toán 5. PAPRICICE – Dây ớt
5.1. Đề bài:
Sau một buổi làm vườn mệt nhọc, Mr. Malnar quyết định tự thưởng cho mình bằng cách thưởng thức các bữa ăn trong ngày cùng với những quả ớt khô do chính tay ông trồng.
Ông có n quả ớt đang phơi trên giá và chúng được nối với nhau bởi n-1 sợi dây. Thế nên, với hai quả ớt bất kì, chúng sẽ được nối với nhau bằng một dãy những sợi dây nào đó. Dễ hiểu hơn, những quả ớt sẽ hình thành một cấu trúc cây

Mr. Malnar sẽ dùng ớt trong cả ba bữa ăn hôm nay. Vì thế, ông sẽ cắt hai dây để chia ớt ra thành ba phần, một phần cho mỗi bữa. Ông biết ăn cay nhiều là không tốt, nên ông muốn chia ớt ra sao cho đều nhất có thế. Vì thế ông sẽ chọn cách cắt dây sao cho: Chênh lệch lượng ớt giữa phần nhiều nhất với phần ít nhất là nhỏ nhất.
Nhiệm vụ của bạn là giúp Mr. Malnar tìm chênh lệch của cách cắt dây tốt nhất.
Dữ liệu vào từ file văn bản PAPRICICE.INP: Gồm nhiều dòng.
- Dòng đầu tiên chứa số nguyên n, số lượng ớt trên giá. Những quả ớt được đánh số từ 1 đến n
- Mỗi dòng trong n-1 dòng tiếp theo chứa hai số nguyên u và v ( 1≤ u, v ≤n) - chỉ số của hai quả ớt được nối trực tiếp bởi một sợi chỉ.
Kết quả ghi ra file văn bản PAPRICICE.OUT:
Gồm một dòng chứa một số nguyên dương là kết quả bài toán - Chênh lệch nhỏ nhất có thể.
| PAPRICICE.INP | PAPRICICE.OUT | PAPRICICE.INP | PAPRICICE.OUT |
|---|---|---|---|
| 4 1 2 2 3 3 4 | 1 | 9 1 3 2 3 3 4 3 5 5 6 5 7 7 8 7 9 | 2 |
Ràng buộc:
𝑆𝑢𝑏𝑡𝑎𝑠𝑘 1∶ 𝑔ồ𝑚 25% số 𝑡𝑒𝑠𝑡 𝑣ớ𝑖 𝑔𝑖ớ𝑖 ℎạ𝑛 3 ≤ 𝑛 ≤ 200
𝑆𝑢𝑏𝑡𝑎𝑠𝑘 2∶ 𝑔ồ𝑚 25% số 𝑡𝑒𝑠𝑡 𝑣ớ𝑖 𝑔𝑖ớ𝑖 ℎạ𝑛 3 ≤ 𝑛 ≤ 2000
𝑆𝑢𝑏𝑡𝑎𝑠𝑘 3∶ 𝑔ồ𝑚 50% số 𝑡𝑒𝑠𝑡 𝑣ớ𝑖 𝑔𝑖ớ𝑖 ℎạ𝑛 3 ≤ 𝑛 ≤ 200000
Bài toán 6. SUMMAX3 – Dán tranh
6.1. Đề bài:
Để 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é!
Dữ liệu vào từ file văn bản SUMMAX3.INP:
- 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 𝑝𝑖,
𝑝𝑖 = 0 thì đỉnh 𝑖 là đỉnh gốc, còn lại 1 ≤ 𝑝𝑖 ≤ 𝑁.
Kết quả ghi ra file văn bản SUMMAX3.OUT:
Một số duy nhất là chi phí dán tranh nhỏ nhất có thể.
Ràng buộc:

Ví dụ:
| SUMMAX3.INP | SUMMAX3.OUT |
|---|---|
| 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 | 23 |
Bài toán 7. SUMMAX4 - Tổng lớn nhất trên cây 4
7.1. Đề bài:
Cho đồ thị dạng cây T 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 𝑎𝑣. Gọi 𝑑𝑖𝑠𝑡(𝑥, 𝑦) là khoảng cách giữa 2 đỉnh 𝑥, 𝑦, khoảng cách được tính bằng số cạnh trên đường đi đơn từ 𝑥 đến 𝑦. Mỗi khi chọn một đỉnh 𝑣 bất kì làm gốc thì ta thu được tổng giá trị của cây là

. Hãy tìm giá trị lớn nhất có thể của cây ban đầu.
Dữ liệu vào từ file văn bản SUMMAX4.INP:
- 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 𝑝𝑖,
𝑝𝑖 = 0 thì đỉnh 𝑖 là đỉnh gốc ban đầu, còn lại 1 ≤ 𝑝𝑖 ≤ 𝑁.
Kết quả ghi ra file văn bản SUMMAX4.OUT:
Một số duy nhất là giá trị lớn nhất có thể của cây.
Ràng buộc:

.
Ví dụ:
| SUMMAX4.INP | SUMMAX4.OUT |
|---|---|
| 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 | 269 |
| 8 9 4 1 7 10 1 6 5 0 1 2 1 1 5 5 5 | 121 |
Bài toán 8. DIAMETER - Đường kính của cây
8.1. Đề bài
Cho một cây T có N đỉnh, hãy tìm khoảng cách xa nhất giữa 2 cặp đỉnh bất kì trên cây. Khoảng cách (𝑢, 𝑣) được xác định bằng số cạnh trên đường đi (𝑢, 𝑣).
Dữ liệu vào từ file văn bản DIAMETER.INP:
- Dòng đầu tiên là số 𝑁 là số đỉnh của đồ thị.
- Dòng tiếp theo có 𝑁 số 𝑝1, 𝑝2, . . 𝑝𝑁 thể hiện có đường đi từ đỉnh 𝑖 đến 𝑝𝑖,
𝑝𝑖 = 0 thì đỉnh 𝑖 là đỉnh gốc ban đầu, còn lại 1 ≤ 𝑝𝑖 ≤ 𝑁.
Kết quả ghi ra file văn bản DIAMETER.OUT:
Một số duy nhất là độ dài đường đi dài nhất.
Ràng buộc:

Ví dụ:
| DIAMETER.INP | DIAMETER.OUT |
|---|---|
| 14 0 1 1 1 2 2 3 4 4 4 5 5 7 7 | 6 |
| 5 4 1 1 0 4 | 3 |
Bài toán 9. FARBORE
9.1. Đề bài
Cho một cây có N đỉnh. Có bao nhiêu cách để đặt N số khác nhau vào cây, mỗi số trên một nút thỏa mãn rằng nút A nhỏ hơn số của tất cả các nút là con của A. Gốc của cây luôn là nút 1. Do kết quả có thể rất lớn nên chỉ cần tìm số dư khi chia kết quả tìm được với 666013.
Dữ liệu vào từ file văn bản FARBORE.INP:
- Dòng đầu tiên ghi số N (1 ≤ N ≤ 100000).
- N − 1 dòng tiếp theo, mỗi dòng ghi 2 số nguyên x và y, thể hiện có một cạnh nối giữa hai đỉnh x và y. (x ≠ y, 1 ≤ x, y ≤ N)
Kết quả ghi ra file văn bản FARBORE.OUT:
In ra một số nguyên duy nhất là kết quả cần tìm
Ví dụ:
| FARBORE.INP | FARBORE.OUT |
|---|---|
| 5 1 2 3 1 2 4 2 5 | 8 |
Giải thích: có 8 cách như sau:







Ràng buộc:
- Subtask 1 (10% số test): N ≤ 7
- Subtask 2 (60% số test): N ≤ 2000
- Subtask 3 (30% số test): Không có ràng buộc gì thêm
- Bài toán 10. STREE
- 10.1. Đề bài:
- Cho một cây nhị phân gồm n nút, các nút được đánh số từ 1 đến n, trong đó nút 1 là nút gốc. Mỗi nút được gán một số nguyên ai. Xét thao tác, tăng hoặc giảm số gán trên một nút, thao tác mất chi phí bằng 1.
- Một cây được gọi là dạng chuẩn nếu các nút lá được gán số 0 hoặc 1, các nút khác được gán giá trị bằng tổng giá trị được gán cho các nút con của nút đó.
- Yêu cầu: Tìm cách đưa cây về dạng chuẩn với chi phí nhỏ nhất.
- Dữ liệu vào từ file văn bản STREE.INP:
- Dòng đầu chứa số nguyên n(n≤5000);
- Dòng thứ hai chứa n số nguyên a1,a2,…,an(|ai|≤100000);
- Tiếp theo là n−1 dòng, mỗi dòng chứa hai số nguyên x,y mô tả một cạnh của cây.
- Kết quả ghi ra file văn bản STREE.OUT:
- Gồm một dòng chứa một số nguyên là chi phí nhỏ nhất để đưa cây về dạng chuẩn.
- Ví dụ:
- STREE.INP
STREE.OUT
3
3 3 3
1 2
1 3
5 - Bài toán 11. SUNWORLD
- 11.1. Đề bài
- Ngoài việc học và thi, Nam cũng có dự định khi đến Hạ Long nhất định phải đi quần thể vui chơi giải trí nổi tiếng là Sun World Ha Long Park.
- Sun World Ha Long Park có n trò chơi trong đó có m trò chơi mạo hiểm (m≤n). Mỗi trò chơi được bố trí ở một địa điểm và có n-1 con đường, mỗi con đường nối chính xác hai địa điểm tổ chức trò chơi. Đảm bảo tất cả các địa điểm đều được kết nối bởi các con đường này. Mỗi con đường Nam mất một phút để đi qua nó.
- Vì là người ưa mạo hiểm nên Nam chỉ chơi những trò mạo hiểm mà thôi, với lại, Nam không có nhiều thời gian nên Nam nhờ các bạn xác định tổng thời gian nhỏ nhất Nam đi trên các con đường để đến tất cả các điểm tổ chức trò chơi mạo hiểm.
- Dữ liệu vào từ file văn bản SUNWORLD.INP:
- Dòng 1 chứa hai số nguyên n và m (2≤m≤n≤100000).
- Dòng 2 chứa m số nguyên khác nhau là số hiệu điểm tổ chức trò chơi mạo hiểm.
- n-1 dòng tiếp theo, mỗi dòng hai số nguyên a và b (0≤a,b≤n-1 ) mô tả một con đường nối điểm tổ chức trò chơi có số hiệu a và b.
- Kết quả ghi ra file văn bản SUNWORLD.OUT:
- Một số nguyên duy nhất là tổng thời gian ít nhất Nam đi qua các con đường để đến tất cả các điểm tổ chức trò chơi mạo hiểm.
- Ví dụ:
- SUNWORLD.INP
SUNWORLD.OUT
7 2
5 0
4 0
3 1
0 6
0 1
2 1
5 2
3 - Giới hạn:
- Subtask 1 (30%): m=2 và n≤100
- Subtask 2 (30%): m≤n≤ 10000
Subtask 3 (40%): n≤ 100000



Bình luận