Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VCOLDWAT - Nước lạnh

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

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.

Được gửi lên bởi:Duc
Ngày:2008-05-24
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:USACO US-Open 2008 - Bảng Đồng

hide comments
2019-01-04 11:09:39
Wisconsin is one of the coldest states of the US, so quite disappointed with the author's knowledge....
2018-09-25 10:51:23
xào xạc lá tre tao nghe sơn sủa
2018-09-07 08:10:08
nhật hào sạch
2018-05-30 19:56:22
cin->sacnf
cout->pritf :3
2017-09-23 05:55:02
1 đấm AC :) DFS tính h[i]
2017-08-19 11:08:57 Con Bò Huyền Thoại
https://kienthuc24h.com/vcoldwat-spoj-nuoc-lanh/
2016-07-11 11:37:53
DFS=AC
2015-09-08 14:14:00
https://thewizard6296.wordpress.com/2015/09/04/5/
2015-08-24 16:06:01
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/08/24/nuoc-lanh-vcoldwat/

Last edit: 2015-10-02 02:21:17
2015-06-11 18:26:22 Thắng Ðam Mê
1 đấm AC, đúng là đêm khuya thanh vắng cầm đt lên code cái ra luôn. DFS cũng ra rồi, code đỡ nhọc hơn(theo mình nghĩ vậy)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.