JOI 2012 Final Camp - Ngày 1

Nhật Bản có \(N\) thành phố, được nối với nhau bằng \(N-1\) con đường hai chiều. Từ một thành phố bất kỳ có thể đi đến mọi thành phố khác bằng các con đường này. Mỗi thành phố có một tòa nhà trụ sở chính quyền; tòa nhà ở thành phố \(i\) cao \(H_i\).

Nhân dịp Olympic Tin học Quốc tế được tổ chức tại Nhật Bản, người ta muốn lên kế hoạch cho một chuyến tham quan để chào đón các thí sinh trên thế giới. Chuyến đi bắt đầu tại một thành phố, liên tiếp đi theo các con đường sang thành phố khác và kết thúc tại một thành phố. Không thành phố nào được ghé thăm quá một lần.

Người ta sẽ trang trí tòa nhà trụ sở chính quyền ở một số thành phố trên hành trình. Nhà thiết kế yêu cầu chiều cao của các tòa nhà được trang trí phải tăng nghiêm ngặt theo thứ tự ghé thăm. Cụ thể, nếu các thành phố có tòa nhà được trang trí lần lượt là \(i_1,i_2,\ldots,i_k\) theo thứ tự trên hành trình, thì phải có

Không bắt buộc phải trang trí tòa nhà tại mọi thành phố đi qua.

Bạn được tự do chọn thành phố bắt đầu, thành phố kết thúc và các thành phố có tòa nhà được trang trí.

Yêu cầu

Hãy tính số tòa nhà lớn nhất có thể trang trí.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\), là số thành phố.
• \(N\) dòng tiếp theo: dòng thứ \(i\) chứa số nguyên \(H_i\), là chiều cao tòa nhà ở thành phố \(i\).
• \(N-1\) dòng tiếp theo: dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\) cách nhau bởi dấu cách, cho biết con đường thứ \(i\) nối thành phố \(A_i\) với thành phố \(B_i\).

Dữ liệu ra

In ra đầu ra chuẩn một số nguyên là số tòa nhà lớn nhất có thể trang trí.

Ràng buộc

• \(2\le N\le100\,000\).
• \(1\le H_i\le1\,000\,000\,000\) với \(1\le i\le N\).
• \(1\le A_i<B_i\le N\) với \(1\le i\le N-1\).
• Các con đường nối tất cả các thành phố thành một mạng liên thông.
• Mọi giá trị trong đầu vào đều là số nguyên.

Phân nhóm

• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(N\le100\).
• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(N\le2\,000\).

Ví dụ

7
4
2
5
3
1
8
7
1 2
2 3
3 4
4 5
3 6
6 7

4

JOI chợt nảy ra ý định nuôi cá. Cửa hàng thú cưng gần nhà cậu đang bán \(N\) con cá. Con cá thứ \(i\) dài \(L_i\) cm và có một trong ba màu: đỏ, xanh lá cây hoặc xanh lam. JOI quyết định chọn ít nhất một con trong số đó để nuôi ở nhà.

Tuy nhiên, nếu nuôi chung cá lớn và cá nhỏ, cá lớn có thể ăn mất cá nhỏ. Cụ thể, nếu chiều dài của cá \(X\) lớn hơn hoặc bằng hai lần chiều dài của cá \(Y\), thì khi nuôi chung, \(X\) sẽ ăn \(Y\). Vì vậy, JOI không được chọn đồng thời hai con cá như thế.

JOI muốn biết có bao nhiêu tổ hợp màu sắc có thể xuất hiện trong những con cá cậu chọn nuôi. Hai tổ hợp được coi là khác nhau nếu số cá của ít nhất một trong ba màu đỏ, xanh lá cây, xanh lam khác nhau. Những cách chọn cá khác nhau nhưng có cùng số cá ở từng màu chỉ được tính là một tổ hợp.

Yêu cầu

Cho chiều dài và màu sắc của từng con cá trong cửa hàng, hãy tính số tổ hợp màu sắc có thể có.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\), là số cá được bán.
• Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa số nguyên \(L_i\) và ký tự \(C_i\), cách nhau bởi dấu cách. \(L_i\) là chiều dài tính bằng cm; R, G, B lần lượt biểu thị màu đỏ, xanh lá cây, xanh lam.

Dữ liệu ra

In ra đầu ra chuẩn trên một dòng số tổ hợp màu sắc có thể có khi chọn ít nhất một con cá và không có con nào ăn con nào.

Ràng buộc

• \(1\le N\le500\,000\).
• \(1\le L_i\le1\,000\,000\,000\) với \(1\le i\le N\).
• \(C_i\) là một trong các ký tự R, G, B.
• \(N\) và mọi \(L_i\) đều là số nguyên.

Phân nhóm

• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(N\le100\).
• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(N\le2\,000\).

Ví dụ

4
10 R
4 G
8 B
5 B

6

10
26 B
10 B
16 G
20 R
6 R
5 G
13 G
40 R
8 R
33 R

13

Bạn muốn làm một lá cờ JOI cấp \(K\) để dùng làm lá cờ mới cho Olympic Tin học Nhật Bản. Cờ JOI được định nghĩa như sau:

• Cờ JOI cấp \(0\) là một bảng \(1\times1\), trong ô duy nhất có một trong các ký tự J, O, I.
• Với số nguyên \(m>0\), cờ JOI cấp \(m\) là một bảng \(2^m\times2^m\), mỗi ô chứa một trong các ký tự J, O, I. Khi chia bảng thành bốn hình vuông \(2^{m-1}\times2^{m-1}\), bốn phần này phải gồm: một cờ JOI cấp \(m-1\), một phần chỉ chứa J, một phần chỉ chứa O và một phần chỉ chứa I. Bốn phần có thể nằm ở các vị trí bất kỳ trong bốn góc.

Chẳng hạn, bảng sau là một cờ JOI cấp \(2\):

OIJJ
JJJJ
OOII
OOII

Bảng sau là một cờ JOI cấp \(3\):

IIIIIIOO
IIIIIIOO
IIIIJOJJ
IIIIOIJJ
JJJJOOOO
JJJJOOOO
JJJJOOOO
JJJJOOOO

Bạn đang có một lá cờ gồm \(2^K\times2^K\) ô, trong đó một số ô đã được viết một ký tự J, O hoặc I. Bạn muốn điền thêm ký tự vào các ô trống và sửa một số ký tự đã có để hoàn thành một cờ JOI cấp \(K\). Viết một ký tự vào ô trống có chi phí \(0\); thay đổi ký tự đã có trong một ô có chi phí \(1\).

Yêu cầu

Hãy tính tổng chi phí nhỏ nhất để hoàn thành lá cờ.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(K,N\) cách nhau bởi dấu cách, lần lượt là cấp của cờ JOI cần tạo và số ô đã có ký tự. Các ký tự đã có được đánh số từ \(1\) đến \(N\).
• Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa \(X_i,Y_i,C_i\) cách nhau bởi dấu cách, cho biết ký tự \(C_i\) nằm ở cột thứ \(X_i\) từ trái sang và hàng thứ \(Y_i\) từ trên xuống.

Dữ liệu ra

In ra đầu ra chuẩn trên một dòng một số nguyên là tổng chi phí nhỏ nhất để tạo cờ JOI cấp \(K\).

Ràng buộc

• \(1\le K\le30\).
• \(1\le N\le1\,000\).
• \(1\le X_i\le2^K\) và \(1\le Y_i\le2^K\) với \(1\le i\le N\).
• \(C_i\) là một trong các ký tự J, O, I.
• Các cặp \((X_i,Y_i)\) đôi một khác nhau.
• \(K,N,X_i,Y_i\) đều là số nguyên.

Phân nhóm

• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn \(K\le10\).

Ví dụ

2 10
2 2 J
3 3 I
1 3 I
1 1 O
3 2 J
2 1 I
4 1 O
3 4 I
4 4 O
2 3 O

3

OI-O
-JJ-
IOI-
--IO

OIJJ
JJJJ
OOII
OOII

4 30
16 14 J
2 8 O
10 9 J
10 13 I
6 6 O
11 14 I
1 2 I
3 2 O
3 10 O
1 12 I
4 11 I
9 5 J
15 1 O
12 4 I
16 5 J
10 7 J
3 8 J
4 10 I
4 7 I
2 11 I
2 12 O
15 5 J
15 7 J
6 9 J
5 7 O
14 5 J
12 11 J
15 10 O
13 16 I
13 11 I

9