trang chủ / đề bài / icpc20_nat_d

Chia vương quốc

Đề bài

Mô tả

Vương quốc Byteland có n thành phố, đánh số từ 1 đến n. Vương quốc có đúng n−1 con đường, mỗi con đường nối một cặp thành phố. Dùng các con đường này, có thể đi từ một thành phố bất kỳ đến mọi thành phố khác.

Nhà vua của Byteland muốn chia vương quốc thành hai nửa và trao mỗi nửa cho một trong hai người con trai. Việc chia được thực hiện bằng cách bỏ đi đúng một con đường, tách vương quốc thành hai thành phần liên thông.

Hóa ra đây không phải là việc đơn giản! Để tránh hai người con tranh chấp, nhà vua cần chia vương quốc một cách công bằng. Với mỗi nửa, nhà vua định nghĩa đường kính của nó là độ dài đường đi đơn dài nhất nối hai thành phố trong nửa đó. Nhà vua muốn hiệu giữa đường kính của hai nửa là nhỏ nhất.

Lưu ý: một đường đi đơn từ thành phố s đến thành phố t là một dãy thành phố v0→v1→v2→…→vk, trong đó v0=s, vk=t và các vi đôi một khác nhau. Với mọi chỉ số i hợp lệ, vi và vi+1 được nối trực tiếp bởi một con đường. Độ dài của đường đi là tổng độ dài các con đường nối vi và vi+1.

Hãy giúp nhà vua!

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu, mỗi bộ dữ liệu có dạng:

  • Dòng đầu tiên chứa một số nguyên dương n (2≤n≤3·105): số thành phố.
  • n−1 dòng tiếp theo, dòng thứ i (i=1…n−1) chứa hai số nguyên pi và li (1≤pi≤i, 1≤li≤109), cho biết hai thành phố pi và i+1 được nối bởi một con đường có độ dài li.

Dữ liệu vào kết thúc bằng một dòng chứa số 0, dòng này không phải là một bộ dữ liệu.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên: hiệu nhỏ nhất giữa đường kính của hai nửa.

Ràng buộc

  • 2≤n≤3·105, tổng n qua tất cả các bộ dữ liệu không vượt quá 106.
  • 1≤pi≤i, 1≤li≤109.

Ví dụ

Input Output Giải thích
12
1 3
1 3
3 2
1 3
1 5
2 1
7 2
8 2
9 3
8 2
11 3
4
1 10
2 10
3 10
4
1 20
2 10
3 10
0
0
0
10
Ở bộ dữ liệu thứ nhất, một cách tối ưu là bỏ con đường nối thành phố 2 và 7: nửa chứa thành phố 7 gồm các thành phố 7,8,9,10,11,12 có đường kính 10→9→8→11→12 dài 3+2+2+3=10; nửa còn lại có đường kính 4→3→1→6 dài 2+3+5=10. Ở bộ thứ ba, bỏ con đường nối thành phố 2 và 3: hai nửa có đường kính 20 và 10.
2
1 5
3
1 4
1 9
3
1 6
2 6
5
1 1
1 2
1 3
1 4
0
0
4
6
5
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: hai nửa đều là một thành phố, đường kính 0. Bộ thứ hai: bỏ con đường dài 9, hai nửa có đường kính 0 và 4. Bộ thứ ba: mọi cách đều cho đường kính 0 và 6. Bộ thứ tư: bỏ con đường dài 4, nửa còn lại có đường kính 2+3=5.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0