Bài tập

Bạn là một nhà phê bình ẩm thực vừa hoàn thành cuộc thi chọn học sinh giỏi văn hóa lớp \(12\) môn Tin học, và bạn bắt đầu du hành qua một đất nước với \(N\) thành phố. Mỗi thành phố có một nhà hàng được đánh giá bằng một số sao, cho thấy mức độ tốt của nó. Đất nước này có \(N - 1\) con đường, sao cho giữa hai thành phố bất kỳ có duy nhất một con đường đơn giản nối chúng lại với nhau.

Là một nhà phê bình ẩm thực rất nghiêm khắc, bạn chỉ ăn ở một nhà hàng mới nếu nó có số sao cao hơn nhà hàng mà bạn đã ăn lần trước. Tuy nhiên, bạn cũng rất thích ăn uống, vì vậy bạn muốn ghé thăm số lượng nhà hàng lớn nhất có thể trong hành trình của mình, tuân theo các quy tắc sau:

• Bạn có thể ăn ở nhiều nhà hàng nhất có thể trong suốt hành trình.
• Bạn không quay lại trên cùng một con đường mà bạn đã đi qua.

Bạn cần lên kế hoạch một hành trình bắt đầu từ một thành phố \(A\) và kết thúc ở một thành phố \(B\), đảm bảo rằng:

• Bạn có thể ăn ở nhiều nhà hàng nhất có thể trong hành trình.
• Bạn không quay lại trên cùng một con đường mà bạn đã đi qua.

Lưu ý rằng bạn không nhất thiết phải ăn ở mỗi thành phố mà bạn đi qua, mà chỉ cần đi qua chúng.

Bạn có thể giúp nhà phê bình tối đa hóa trải nghiệm ăn uống của mình không?

Input

• Dòng đầu tiên chứa một số nguyên \(N\), là số thành phố.
• Dòng thứ hai chứa \(N\) số nguyên, số nguyên thứ \(i\) là số sao của nhà hàng tại thành phố \(i\).
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\), chỉ ra một con đường giữa các thành phố \(u\) và \(v\).

Output

In ra số lượng nhà hàng tối đa mà nhà phê bình có thể ăn tại, dưới các ràng buộc đã cho.

Example

6
4 1 3 2 5 3
1 2
1 3
1 4
4 5
4 6

3

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

4

6
1 1 1 1 1 1
1 2
1 3
1 4
4 5
4 6

1

Scoring

• \(2 \leq N \leq 10^5\).
• \(1 \leq S_{i} \leq 10^5\), với \(S_{i}\) là số sao của nhà hàng tại thành phố \(i\).
• \(1 \leq u \neq v \leq N\), với mọi cặp \((u, v)\).

\(25\%\) số điểm có \(N \leq 20\).

\(25\%\) số điểm có \(20 < N \leq 100\).

\(25\%\) số điểm có \(100 < N \leq 50000\).

\(20\%\) số điểm có \(50000 < N \leq 100000\).

Trong một hệ thống xử lý tín hiệu số, có \(n\) bộ phát được đánh số từ \(1\) đến \(n\). Bộ phát thứ \(i\) có cường độ tín hiệu là \(a_i\).

Mỗi mã truy vấn \(x\) biểu diễn một tập các đặc tính tín hiệu cần thiết dưới dạng nhị phân. Một bộ phát thứ \(i\) được xem là tương thích với mã \(x\) nếu nó chứa đầy đủ tất cả các bit \(1\) xuất hiện trong biểu diễn nhị phân của \(x\).

Nói cách khác, bộ phát thứ \(i\) tương thích với \(x\) khi \(x & i = x\), trong đó \(&\) là phép toán AND trên bit.

Với mỗi số nguyên dương \(x\), ta định nghĩa trọng số của \(x\) là:

tức là tổng cường độ của tất cả các bộ phát thứ \(i\) thỏa mãn \(x & i = x\).

Yêu cầu: Hãy tính lần lượt các giá trị \(f(1), f(2), \ldots, f(2^{\lfloor \log_2 n \rfloor + 1} - 1)\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) — số lượng bộ phát \((1 \leq n \leq 10^6)\).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) — cường độ tín hiệu của các bộ phát \((|a_i| \leq 10^9)\).

Output

• In ra lần lượt các giá trị \(f(1), f(2), \ldots, f(2^{\lfloor \log_2 n \rfloor + 1} - 1)\) trên một dòng, các giá trị cách nhau bởi một dấu cách.

Example

3
3 2 1

4 3 1 

Scoring

• Subtask 1 (30 điểm): \(1 \leq n \leq 1000\).

• Subtask 2 (30 điểm): \(1 \leq n \leq 100000\).

• Subtask 3 (40 điểm): Không có ràng buộc gì thêm.

Trên hành tinh Pandora, chủng tộc Navi đang phải đối mặt với cuộc xâm lăng của người Trái Đất. Người Trái Đất đã cử \(n\) robot với lượng máu tương ứng là \(a_1, a_2, \ldots, a_n\). Để bảo vệ quê hương, \(m\) dũng sĩ Navi đã ra trận, mỗi dũng sĩ thứ \(j\) có sức tấn công là \(b_j\).

Theo tín ngưỡng của người Navi, họ yêu chuộng hòa bình nên mỗi dũng sĩ chỉ tấn công một robot duy nhất. Một dũng sĩ Navi thứ \(j\) có thể tiêu diệt được một robot thứ \(i\) nếu sức tấn công của dũng sĩ đó lớn hơn hoặc bằng lượng máu của robot (\(b_j \ge a_i\)).

Với danh sách lượng máu của \(n\) robot và sức tấn công của \(m\) dũng sĩ Navi, hãy tìm số lượng robot tối đa mà các dũng sĩ Navi có thể tiêu diệt.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) (\(1 \le n, m \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)), là lượng máu của các robot.
• Dòng thứ ba chứa \(m\) số nguyên dương \(b_1, b_2, \ldots, b_m\) (\(1 \le b_j \le 10^9\)), là sức tấn công của các dũng sĩ Navi.

Output

Số lượng Robot nhiều nhất mà các chiến binh Navi có thể tiêu diệt được (Lưu ý: mỗi chiến binh Navi chỉ tấn công một robot duy nhất)

Example

3 2
1 2 3
1 1

1

Scoring

• Subtask 1 (10% số điểm): \(a_i = b_j = 1\) với mọi \(1 \le i \le n\) và \(1 \le j \le m\).
• Subtask 2 (30% số điểm): \(b_1 = b_2 = \dots = b_m\).
• Subtask 3 (60% số điểm): Không có ràng buộc bổ sung.

Cho dãy số \(a_1, a_2, \ldots, a_n\). Ta có định nghĩa median của một dãy số như sau:

• Nếu độ dài dãy là lẻ thì median = phần tử giữa của dãy sau khi sắp xếp. Ví dụ \(a = \{1, 2, 3\}\) thì median = 2.
• Nếu độ dài dãy là chẵn thì median = trung bình cộng của hai phần tử giữa của dãy sau khi sắp xếp. Ví dụ \(a = \{1, 2, 3, 4\}\) thì median = 2.5.

Yêu cầu: Cho \(n\) số nguyên, với mỗi lần nhập \(a_i\), bạn phải thực hiện:

• Thêm \(a_i\) vào dãy số.
• Tính median cho dãy số mới cập nhật.
• In ra median của các dãy số mới cập nhật trên từng dòng, mỗi median in ra theo định dạng 1 chữ số thập phân sau dấu phẩy.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \leq n \leq 10^5)\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(a_i\) \((0 \leq a_i \leq 10^5)\).

Output

• Ghi ra \(n\) số thực trên \(n\) dòng theo thứ tự là median của các dãy số.

Example

6
12
4
5
3
8
7

12.0
8.0
5.0
4.5
5.0
6.0

Scoring

• \(20\%\) số test có \(n \leq 100\).
• \(30\%\) số test có \(n \leq 1000\).
• \(20\%\) số test có dãy \(a\) là \(1\) dãy tăng dần.
• \(30\%\) còn lại không có ràng buộc gì thêm.