trang chủ / đề bài / icpc22_mb_j

Những chấm tròn

Đề bài

Mô tả

Mika rất thích vẽ nguệch ngoạc vào vở. Hôm nay, cô vẽ N chấm và nối chúng bằng N−1 đoạn thẳng. Các đoạn thẳng được vẽ sao cho cô có thể đi theo một đường từ một chấm bất kỳ tới một chấm bất kỳ khác mà không phải nhấc bút.

Các chấm được đánh số từ 0 đến N−1. Mika muốn đi theo một đường từ chấm 0 tới một chấm nào đó mà không nhấc bút. Đường đi được phép đi qua một đoạn thẳng nhiều lần. Độ dài đường đi là số lần đi dọc theo một đoạn thẳng (mỗi lần đi qua một đoạn thẳng được tính một lần).

Để tăng thử thách, cô gán N số nguyên E0,E1,…,EN−1 cho các chấm. Với mọi chấm i, cô phải đảm bảo đường đi của mình rời khỏi chấm đó không quá Ei lần.

Với mỗi i từ 0 đến N−1, hãy xác định độ dài lớn nhất của đường đi Mika có thể đi từ chấm 0 tới chấm i thỏa mãn các điều kiện trên.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên N là số chấm (1≤N≤50000).

Dòng thứ hai chứa N số nguyên E0,E1,…,EN−1 (1≤Ei≤40000), trong đó Ei là số lần nhiều nhất đường đi được rời khỏi chấm i. Đảm bảo Ei lớn hơn hoặc bằng số đoạn thẳng xuất phát từ chấm i.

N−1 dòng tiếp theo, mỗi dòng chứa hai số nguyên Ui và Vi (0≤Ui,Vi≤N−1), cho biết có một đoạn thẳng nối chấm Ui và chấm Vi.

Dữ liệu ra

Với mỗi i từ 0 đến N−1, in ra một dòng chứa độ dài lớn nhất của đường đi kết thúc tại chấm i.

Ràng buộc

  • 1≤N≤50000.
  • 1≤Ei≤40000, Ei không nhỏ hơn số đoạn thẳng xuất phát từ chấm i.
  • Các đoạn thẳng tạo thành một cây (đi được giữa hai chấm bất kỳ).

Ví dụ

Input Output Giải thích
3
2 6 2
0 1
1 2
8
7
8
Kết thúc tại chấm 0: 0→1→2→1→2→1→0→1→0 rời chấm 0 hai lần, chấm 1 bốn lần, chấm 2 hai lần, độ dài 8. Kết thúc tại chấm 1: chấm 0 chỉ được rời 2 lần nên đoạn 0−1 được đi tối đa 3 lần, tổng 7.
7
1 4 3 3 1 1 2
0 1
6 1
1 5
1 2
2 4
6 3
12
13
12
13
13
12
14
Đường đi phải liền mạch: muốn đi đoạn 6−3 thì phải đi qua đoạn 1−6 trước. Với chấm cuối là 0, mọi đoạn thẳng được đi đúng hai lần (mỗi chiều một lần), độ dài 12.

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