1. Bài toán: Tìm đường đi dài nhất trong cây                             ti35_dh25

Cho một cây không trọng số. Độ dài của một đường đi trong cây là số cạnh đi qua từ nút nguồn tới nút đích.

Yêu cầu: Hãy viết chương trình tìm đường đi dài nhất trong cây.

Dữ liệu vào từ file văn bản PT07Z.INP:

•   Dòng đầu tiên chứa một số nguyên 𝑁 là số nút trong cây (0 < 𝑁 ≤ 10^4).

•   𝑁-1 dòng sau, mỗi dòng chứa hai số (𝑢, 𝑣) mô tả một cạnh của cây (1 ≤ 𝑢, 𝑣 ≤ 𝑁).

Kết quả đưa ra file văn bản PT07Z.OUT:

Một số nguyên duy nhất là độ dài đường đi dài nhất trong cây đó.

Ví dụ:

PT07Z.INPPT07Z.OUT 
3
1 2
2 3
2 

Ràng buộc:

• Có 50% số test tương ứng 20% số điểm có 𝑁 ≤ 10^3

• 50% số test còn lại tương ứng 50% số điểm có 10^3 < 𝑁 ≤ 10^4

2.  SUMMAX1 - Nhánh có tổng lớn nhất 1

1.1. Đề bài:

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 𝑎𝑖, 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?

Dữ liệu vào từ file văn bản SUMMAX1.INP:

  • Dòng đầu tiên là số 𝑁 là số đỉnh của đồ thị (𝑁 ≤ 2.10^5);
  • 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ự (𝑎𝑖 ≤ 10^9);
  • Dòng tiếp theo có 𝑁 số 𝑝1, 𝑝2, . . 𝑝𝑁 thể hiện có đường đi từ đỉnh 𝑖 đến 𝑝𝑖 với  𝑝1 = 0 vì đỉnh 1 là gốc cây ban đầu, còn lại 1 ≤ 𝑝𝑖 ≤ 𝑁.

Kết quả ghi ra file văn bản SUMMAX1.OUT:

Một số duy nhất là đường đi có tổng lớn nhất.

Ví dụ:

SUMMAX1.INPSUMMAX1.OUT
14
3 2 1 10 1 3 9 1 5 3 4 5 9 8
0 1 1 1 2 2 3 44 4 5 5 7 7
22

3. SUMMAX2 - Nhánh có tổng lớn nhất 2

2.1. Đề bài:

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?

Dữ liệu vào từ file văn bản SUMMAX2.INP:

  • Dòng đầu tiên là số 𝑁 là số đỉnh của đồ thị (𝑁 ≤ 2.10^5);
  • 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ự (𝑎𝑖 ≤ 10^9);
  • Dòng tiếp theo có 𝑁 số 𝑝1, 𝑝2, . . 𝑝𝑁 thể hiện có đường đi từ đỉnh 𝑖 đến 𝑝𝑖 với  𝑝i = 0 thì đỉnh i là gốc cây ban đầu, còn lại 1 ≤ 𝑝𝑖 ≤ 𝑁.

Kết quả ghi ra file văn bản SUMMAX2.OUT:

Một số duy nhất là đường đi có tổng lớn nhất.

Ví dụ:

SUMMAX2.INPSUMMAX2.OUT
14
3 2 1 10 1 3 9 1 5 3 4 5 9 8
0 1 1 1 2 2 3 44 4 5 5 7 7
41

4. DISTK - Khoảng cách K trên cây

Cho một cây T[1] có N đỉnh, các đỉnh được đánh số từ 1 đến N, và một số K, hãy đếm xem có bao nhiêu cặp đỉnh (u,v) mà có khoảng cách đúng bằng K. Khoảng cách được tính bằng số cạnh. Chú ý: cặp (u, v) và cặp (v, u) là như nhau.

Dữ liệu vào từ file văn bản DISTK.INP:

  • Dòng đầu tiên có 2 số N và K (1 ≤ 𝑁 ≤ 50000, 1 ≤ 𝐾 ≤ 200)
  • Dòng tiếp theo có 𝑁 số 𝑝1, 𝑝2, . . 𝑝𝑁 thể hiện có đường đi từ đỉnh 𝑖 đến 𝑝𝑖, 𝑝1 = 0 vì đỉnh 1 là đỉnh gốc, còn lại 1 ≤ 𝑝𝑖 ≤ 𝑁.

Kết quả ghi ra file văn bản DISTK.OUT:

Một số duy nhất số cặp đỉnh có khoảng cách K.

Ví dụ:

DISTK.INPDISTK.OUT
5 2
0 1 2 3 2
4

5. – Đường đi dài nhất

4.1. Đề bài:

Cho đồ thị có hướng không có chu trình với n đinht và m cạnh (các đỉnh được đánh số từ 1 đến n). Mỗi cạnh được gán một trọng số là một số nguyên có trị tuyệt đối không vượt quá 10^9

Hãy tìm đường đi trọng số lớn nhất từ đỉnh s đến đinh t của đồ thị (trọng số của đường đi được tính bằng tổng trọng số tất cả các cạnh trên đường đi đó)

Dữ liệu vào từ file văn bản DPDAG.INP:

  • Dòng 1 chứa số nguyên dương n, m ≤ 10^5;
  • m dòng tiếp theo mỗi dòng chứa 3 số nguyên ), thể hiện cung có trọng số w.
  • Dòng cuối chứa 2 số

Kết quả ghi ra file văn bản DPDAG.OUT:

Ghi một số nguyên duy nhất là trọng số lớn nhất của đường đi từ s đến t. Nếu không có đường đi từ s đến t ghi NO PATH.

Ví dụ:

DPDAG.INPDPDAG.OUTGiải thích
6 8
1 5 10
1 4 2
1 2 1
5 4 10
5 6 3
4 2 10
4 3 6
2 3 10
1 3
40Đường đi dài nhất là: 1 à 5 à 4 à 2 à 3