TREECST - Tree Construction

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/treecst


Xây dựng cây

Cho một cây có N đỉnh. Tìm cách xóa đi một cạnh thuộc cây và thêm vào một cạnh mới, sao cho sau đó, độ dài đường đi dài nhất trên cây là nhỏ nhất có thể. Độ dài của một đường đi được tính bằng số cạnh thuộc đường đi đó.

Dữ liệu

Dòng đầu tiên chứa số N (1 ≤ N ≤ 300 000).

N-1 dòng sau, mỗi dòng chứa 2 số nguyên mô tả một cạnh của cây.

Kết quả

  • Dòng đầu tiên in ra độ dài nhỏ nhất tìm được.
  • Dòng thứ hai ghi 2 số nguyên cho biết cạnh cần xóa.
  • Dòng thứ ba ghi 2 số nguyên cho biết cạnh cần thêm vào.

Nếu có nhiều lời giải, chỉ cần in ra một lời giải bất kỳ.Ví dụ

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

Kết quả
2
3 4
4 2

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

Kết quả
3
2 3
7 3


Được gửi lên bởi:Jimmy
Ngày:2008-10-22
Thời gian chạy:3s
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:COCI 2008-2009

hide comments
2019-07-10 16:15:28
thật ra tràn stack là do ngu chứ không phải do thiếu pragma
2018-07-02 18:29:47
ĐM stack T.T
UPD: bác nào tràn stack thì thêm dòng này vào đầu code nha :v
#pragma comment(linker, "/STACK: 2000000")

Last edit: 2018-07-02 18:47:27
2018-06-20 09:50:43
dfs thuong co lon ac
2018-06-20 09:29:32
thao khảo thuật toán và code : https://bit.ly/2K4I5Yc
2018-06-20 09:27:40
dfs thường rồi cout độ dài auto AC
2016-02-17 20:30:14
đm stack T.T
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.