trang chủ / đề bài / icpc26_nat_d

Thứ tự tuyệt vời

Đề bài

Mô tả

Vương quốc Exordia có n thành phố, được đánh số từ 0 đến n−1. Các thành phố được nối với nhau bởi n−1 con đường hai chiều sao cho có thể đi lại giữa hai thành phố bất kỳ bằng một hoặc nhiều con đường trong số này.

Nữ hoàng ERB, người trị vì vương quốc, hằng năm đều đi vi hành để tìm hiểu cuộc sống thường ngày của người dân. Bà luôn di chuyển theo các quy tắc sau.

Ban đầu, Nữ hoàng ERB ở thủ đô (thành phố 0), thành phố này được coi là đã thăm. Sau đó, bà lặp lại các bước sau:

  • Nếu có ít nhất một thành phố chưa thăm nối trực tiếp với thành phố hiện tại, bà đi tới thành phố có số hiệu nhỏ nhất trong số đó. Thành phố đó trở thành đã thăm.
  • Ngược lại, nếu bà đang ở thủ đô, chuyến đi kết thúc.
  • Ngược lại, bà quay về thành phố mà từ đó bà đã đi tới thành phố hiện tại trong lần đầu tiên.

Dãy thăm lần đầu là dãy các thành phố theo thứ tự chúng được thăm lần đầu tiên. Lưu ý rằng dãy này luôn bắt đầu bằng thành phố 0 và chứa mỗi thành phố đúng một lần.

Để cải thiện giao thông trong vương quốc, Nữ hoàng ERB quyết định xây đúng một con đường mới giữa một cặp thành phố chưa được nối trực tiếp với nhau. Tuy nhiên, đội cận vệ hoàng gia đã lên kế hoạch hộ tống bí mật theo lộ trình hiện tại của bà, nên bà muốn dãy thăm lần đầu giữ nguyên hoàn toàn sau khi con đường mới được xây.

Bạn được Nữ hoàng giao nhiệm vụ đếm số cách xây con đường mới sao cho dãy thăm lần đầu không thay đổi. Hai cách được coi là khác nhau nếu con đường mới nối hai cặp thành phố khác nhau. Bạn có giúp được bà không?

Dữ liệu vào

Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu τ (1≤τ≤104). Tiếp theo là mô tả các bộ dữ liệu.

  • Dòng đầu tiên của mỗi bộ dữ liệu chứa số nguyên n (3≤n≤2·105), số thành phố.
  • Dòng thứ i trong n−1 dòng tiếp theo chứa hai số nguyên ui và vi (0≤ui,vi<n, ui≠vi), hai thành phố được nối bởi con đường thứ i. Dữ liệu đảm bảo các con đường đã cho nối tất cả n thành phố.

Dữ liệu đảm bảo tổng n qua tất cả các bộ dữ liệu không vượt quá 2·105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là số cách xây con đường mới.

Ràng buộc

  • 1≤τ≤104.
  • 3≤n≤2·105; 0≤ui,vi<n, ui≠vi; các con đường tạo thành một cây.
  • Tổng n qua tất cả các bộ dữ liệu không vượt quá 2·105.

Ví dụ

Input Output Giải thích
2
4
0 2
2 1
2 3
5
0 2
0 3
3 1
3 4
2
3
Bộ thứ nhất: các con đường là 0−2, 2−1, 2−3. Nữ hoàng đi qua các thành phố theo thứ tự [0,2,1,2,3,2,0] nên dãy thăm lần đầu là [0,2,1,3]. Có 3 cặp thành phố chưa được nối trực tiếp: (0,1), (0,3) và (1,3). Nếu xây đường (0,1), dãy mới là [0,1,2,3]; nếu xây (0,3) hoặc (1,3), dãy vẫn là [0,2,1,3]. Vậy có 2 cách: (0,3) và (1,3). Bộ thứ hai: các con đường là 0−2, 0−3, 3−1, 3−4; có 3 cách giữ nguyên dãy thăm lần đầu: (0,4), (1,4), (2,3).
3
3
1 0
2 0
6
0 4
4 2
4 5
0 1
1 3
3
0 1
1 2
1
5
1
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: dãy thăm lần đầu là [0,1,2], xây đường (1,2) vẫn giữ nguyên dãy. Bộ thứ hai: dãy thăm lần đầu là [0,1,3,4,2,5]; 5 cách là (0,3), (0,5), (1,4), (3,4), (2,5). Bộ thứ ba: chỉ có cặp (0,2), và từ 0 Nữ hoàng vẫn đi tới 1 trước.

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