Hotline : +84 0988.131.808       endefr
  1. Hanh Tram
  2. Thảo luận Internet CNTT
  3. Thứ năm, Tháng 3 16 2017, 02:39 PM
  4.  Đăng ký qua email

Mùa hè oi ả ở Wisconsin đã khiến cho lũ bò phải đi tìm nước để làm dịu đi cơn khát. Các đường ống dẫn nước của nông dân John đã dẫn nước lạnh vào 1 tập N (3 <= N <= 99999; N lẻ) nhánh (đánh số từ 1..N) từ một cái bơm đặt ở chuồng bò.

Khi nước lạnh chảy qua các ống, sức nóng mùa hè sẽ làm nước ấm lên. Bessie muốn tìm chỗ có nước lạnh nhất để cô bò có thể tận hưởng mùa hè một cách thoải mái nhất.

Bessie đã vẽ sơ đồ toàn bộ các nhánh ống nước và nhận ra rằng nó là một đồ thị dạng cây với gốc là chuồng bò và ở các điểm nút ống thì có chính xác 2 nhánh con đi ra từ nút đó. Một điều ngạc nhiên là các nhánh ống này đều có độ dài là 1.

Cho bản đồ các ống nước, hãy cho biết khoảng cách từ chuồng bò tới tất cả các nút ống và ở các phần cuối đường ống.

“Phần cuối” của một đường ống, có thể là đi vào một nút ống hoặc là bị bịt, được gọi theo số thứ tự của đường ống. Bản đồ có C (1 <= C <= N) nút ống, được mô tả bằng 3 số nguyên: là “phần cuối” của ống E_i (1 <= E_i <= N) và 2 ống nhánh đi ra từ đó là B1_i và B2_i (2 <= B1_i <= N; 2 <= B2_i <= N). Đường ống số 1 nối với chuồng bò; khoảng cách từ phần cuối của đường ống này tới chuồng bò là 1.

Dữ liệu

  • Dòng 1: 2 số nguyên cách nhau bởi dấu cách: N và C
  • Dòng 2..C+1: Dòng i+1 mô tả nút ống i với ba Số nguyên cách nhau bởi dấu cách: E_i, B1_i, và B2_i
Bình luận
Không có ý kiến đóng góp nào.
Thêm bình luận
Hải Hoàn Chấp nhận Trả lời
0
Bầu chọn

Kết quả

  • Dòng 1..N: Dòng i chứa 1 số nguyên là khoảng cách từ chuồng tới “phần cuối” của ống thứ i.

Ví dụ

Dữ liệu
5 2
3 5 4
1 2 3

Giải thích:
Dữ liệu ở trên mô tả bản đồ ống nước sau:

                    +--------+
                    | Chuồng |
                    +--------+
                       | 1
                       *
                    2 / \ 3
                         *
                      4 / \ 5

Kết quả
1
2
2
3
3

Giải thích:
Ống 1 luôn cách chuồng 1 đoạn là 1. Ống 2 và 3 nối với ống 
1 nên khoảng cách sẽ là 2. Ống 4 và 5 nối với ống 3 nên 
khoảng cách sẽ là 3.
Bình luận
Không có ý kiến đóng góp nào.
Thêm bình luận
  1. hơn một tháng trước đây
  2. Thảo luận Internet CNTT
  3. Trả lời này
  • Trang :
  • 1


Không có trả lời ở đây.
khách
Gửi phản hồi của bạn
Tải lên tập tin hoặc hình ảnh cho cuộc thảo luận này bằng cách nhấp vào nút tải ở dưới. hỗ trợ gif,jpg,png,zip,rar
• Xóa s (Maximum File Size: 2 MB)
Bạn có thể chèn các thăm dò ý kiến vào bài viết của bạn. Các cuộc thăm dò sau đó sẽ xuất hiện trong bài viết.
Tùy chọn bỏ phiếu
Chia sẻ vị trí

Chia sẻ vị trí hiện tại của bạn trong khi đăng một câu hỏi mới cho phép người xem để xác định vị trí bạn đang nằm.

Vi độ:
Kinh độ:
  • Bùi Văn Lương
    1897.00 Điểm
  • Hoàng Tiến An
    1502.00 Điểm
  • Phạm Minh Anh
    1335.00 Điểm
  • Hoàng Trung Kiên
    1197.00 Điểm
  • Nguyễn Anh Đông
    1165.00 Điểm
  • Nguyễn Văn Cường
    1042.00 Điểm
  • Hoàng Mạnh Thái
    942.00 Điểm
  • Hoàng Anh Thư
    815.00 Điểm
  • Hoàng Thế Anh
    792.00 Điểm
  • Triệu Hùng Cường
    692.00 Điểm
  • Hoàng Thị Mai
    625.00 Điểm
  • Triệu Mai Anh
    237.00 Điểm
  • Lưu Phương Dung
    162.00 Điểm
  • Phạm Thị Hồng
    142.00 Điểm
  • Hoàng Thế Quỳnh
    87.00 Điểm