# Bài 1: cstation

> Time limit: 1s
> Memory limit: 1GB
> Dạng bài: Batch

## Tóm tắt đề bài

Cho một cây gồm $N$ đỉnh, các đỉnh được đánh số từ $0$ đến $N-1$. Các cạnh được đánh số từ $0$ đến $N-2$, trong đó cạnh thứ $i$ ($0\le i\le N-2$) nối trực tiếp hai đỉnh $A_i$ và $B_i$.

Có $K$ tuyến đường trên cây được cho là **tuyến đường trọng điểm**, các tuyến đường được đánh số từ $0$ đến $K-1$. Trong đó, tuyến đường trọng điểm thứ $i$ ($0\le i\le K-1$) là đường đi ngắn nhất xuất phát từ đỉnh $U_i$ và kết thúc tại đỉnh $V_i$.

Trong $Q$ ngày tiếp theo, mỗi ngày ban quy hoạch đô thị sẽ chọn ra một **tuyến đường tiềm năng**. Trong ngày thứ $i$ ($0\le i\le Q-1$), tuyến đường tiềm năng mà ban quy hoạch chọn sẽ là con đường ngắn nhất xuất phát từ đỉnh $X_i$ và kết thúc tại đỉnh $Y_i$. Tuyến đường này trong ngày thứ $i$ sẽ được coi là **tuyến đường trọng điểm thứ $K$**.

Với mỗi ngày, ban quy hoạch muốn chọn ra một số đỉnh trên cây và đặt trạm tại các đỉnh đó sao cho với mọi tuyến đường trọng điểm được đánh số từ $0$ đến $K$, đều có ít nhất một trạm được đặt trên các tuyến đường đó.

**Yêu cầu:** Giả sử bạn là một thành viên của ban quy hoạch đô thị, hãy viết một chương trình để giải quyết vấn đề trên.

## Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

vector<int> solve(int N, int K, int Q, const vector<int>& A, const vector<int>& B, const vector<int>& U, const vector<int>& V, const vector<int>& X, const vector<int>& Y);

- Hàm này cần trả về một `vector<int>` bao gồm $Q$ phần tử, trong đó phần tử thứ $i$ ($0\le i\le Q-1$) tương ứng với số trạm tối thiểu cần phải đặt khi xét ngày thứ $i$.
- Hàm này sẽ được gọi $T$ lần, mỗi lần gọi tương ứng với một trường hợp thử nghiệm.

**Lưu ý:**
- Chương trình của bạn cần phải khai báo thư viện `"cstationlib.h"` ở đầu.
- Trong chương trình của bạn, bạn được phép khai báo và gọi các hàm khác, nhưng không được phép chứa hàm `main()`.

## Ràng buộc

- $1\le N,K,Q\le 10^5$
- $0\le A_i,B_i\le N-1$ với mọi $i$ từ $0$ đến $N-2$
- $0\le U_i,V_i\le N-1$ với mọi $i$ từ $0$ đến $K-1$
- $0\le X_i,Y_i\le N-1$ với mọi $i$ từ $0$ đến $Q-1$
- $A_i\ne B_i$ với mọi $i$ từ $0$ đến $N-2$
- $\sum_N,\sum_K,\sum_Q\le 2\times 10^5$

## Scoring

- Subtask $1$ ($5$ điểm): $1\le N,K,Q\le 14; T\le 50$
- Subtask $2$ ($10$ điểm): $\sum_N,\sum_K,\sum_Q\le 500$
- Subtask $3$ ($10$ điểm): $\sum_N,\sum_K,\sum_Q\le 3000$
- Subtask $4$ ($20$ điểm): $A_i=i,B_i=i+1$ với mọi $i$ từ $0$ đến $N-2$
- Subtask $5$ ($55$ điểm): Không có ràng buộc gì thêm

# Bài 2: colorful

> Time limit: 2s
> Memory limit: 1GB
> Dạng bài: Interactive

## Tóm tắt đề bài

Có một đống bóng gồm $N$ quả, các quả bóng được đánh số từ $0$ đến $N-1$. Mỗi quả bóng trong đống có thể có màu từ $0$ đến $K-1$, trong đó quả bóng thứ $i$ ($0\le i\le N-1$) có màu $A_i$ ($0\le A_i\le K-1$). Đảm bảo với mọi $j$ từ $0$ đến $K-1$, tồn tại một quả bóng trong đống bóng có màu $j$.

**Lưu ý:** Bạn được biết trước giá trị của $N$, tuy nhiên bạn không biết chính xác giá trị của $K$.

Bạn không biết chính xác màu của các quả bóng, và bạn muốn tìm cách xác định nó. Để làm được việc này, bạn được phép thực hiện một số câu hỏi. Với mỗi câu hỏi:
- Bạn chọn một tập con gồm một số quả bóng trong $N$ quả.
- Sau đó, bạn sẽ biết được số lượng màu khác nhau xuất hiện trong các quả bóng được chọn có lớn hơn hoặc bằng $\lfloor \frac{K+1}2\rfloor$ hay không (trong đó, $\lfloor x\rfloor$ là số nguyên gần nhất nhỏ hơn hoặc bằng $x$).

**Yêu cầu:** Hãy viết một chương trình tương tác mô phỏng quá trình xác định màu của các quả bóng. Vì có thể có nhiều trạng thái màu khác nhau của $N$ quả bóng, bạn chỉ cần xác định một trạng thái **đẳng cấu** với trạng thái gốc. Cụ thể:
- Gọi $B_i$ là trạng thái màu của các quả bóng mà bạn dự đoán. Khi đó với mọi cặp số $(i,j)$ ($0\le i,j\le N-1,i\ne j$):
- Nếu $A_i=A_j$ thì $B_i=B_j$.
- Nếu $A_i\ne A_j$ thì $B_i\ne B_j$.

## Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

vector<int> solve(int N);

- $N$ là số quả bóng trong đống bóng cho trước.
- **Lưu ý**: Bạn chỉ được biết giá trị của $N$ nhưng không được biết giá trị của $K$.
- Hàm này cần trả về một `vector<int>` tương ứng với trạng thái màu của các quả bóng mà bạn dự đoán. Bạn không cần xác định chính xác trạng thái màu của các quả bóng, nhưng đáp án của bạn phải **đẳng cấu** với trạng thái của các quả bóng ban đầu.
- Hàm này được gọi nhiều lần, mỗi lần gọi tương ứng với một trường hợp thử nghiệm.

Trong hàm `solve()`, bạn được phép gọi hàm sau:

bool ask(vector<int> pos);

- $pos$ là một `vector<int>` bao gồm chỉ số của tất cả quả bóng được chọn. Cần phải đảm bảo các phần tử trong mảng $pos$ là các chỉ số quả bóng hợp lệ, và các giá trị trong mảng $pos$ phải đôi một phân biệt.
- Hàm này sẽ trả về `true` nếu như số màu khác nhau trong đống bóng được chọn lớn hơn hoặc bằng $\lfloor \frac{K+1}2\rfloor$, ngược lại hàm sẽ trả về `false`.
- Với mỗi trường hợp thử nghiệm, hàm `solve()` được gọi hàm `ask()` tối đa $14000$ lần.

**Lưu ý:**
- Chương trình của bạn cần phải khai báo thư viện `"colorfullib.h"` ở đầu.
- Trong chương trình của bạn, bạn được phép khai báo và gọi các hàm khác, nhưng không được phép chứa hàm `main()`.
- *Trong đề không nói gì về việc trình chấm có thích ứng hay không (nếu mọi người có thì cho em xin thông tin này với ạ).*

## Ràng buộc

- $3\le K\le 32$
- $K\le N\le 256$
- $\sum_N\le 2\times 10^4$

## Scoring

- Subtask $1$ ($10$ điểm): $N\le 10;K\le 3$
- Subtask $2$ ($20$ điểm): $N\le 10$
- Subtask $3$ ($70$ điểm): Không có ràng buộc gì thêm

## Cách tính điểm

Gọi $K$ là số lần gọi hàm `ask()` tối đa trong tất cả lần gọi hàm `solve()` của một test. Khi đó điểm của bạn được tính như sau:

| Giá trị $K$ |Phần trăm số điểm|
|--------------------|-----------------|
| $K\le 1400$ | $100\%$ |
|$1400\le K\le 14000$|$\frac{1400}K\times 100\%$|
| $K>14000$ | $0\%$ |

Điểm của một subtask bằng phần trăm điểm tối thiểu của một test trong subtask đó nhân với số điểm tối đa của subtask.

# Bài 3: magician

> Time limit: 2s
> Memory limit: 1GB
> Dạng bài: Two-step

## Tóm tắt đề bài

Hôm nay, Alice và Bob sẽ thực hiện một trò ảo thuật trước mặt hàng trăm khán giả. Trò ảo thuật mà hai người sẽ làm có thể được mô tả như sau:
- Đầu tiên, Bob bị bịt mắt, Alice gọi một khán giả bất kỳ lên. Khán giả sẽ chọn $N$ là bái trong đống bài $52$ lá Alice đã chuẩn bị.
- Từ đống bài đó, khán giả sẽ vẽ một cây **có gốc** gồm $N$ đỉnh, mỗi đỉnh tương ứng với một lá bài.
- Tiếp theo, Alice sẽ viết một số nguyên dương ở sau tất cả lá bài khán giả đã chọn.
- Sau đó, Alice sẽ xáo lại các lá bài và đưa cho Bob đống bài vừa xáo. Bob không được nhìn mặt trước của các lá bài mà chỉ được nhìn các số nguyên dương mà Alice đã viết trên đó.
- Từ dữ kiện trên, Bob sẽ dựng lại cây mà khán giả đã vẽ. Trò ảo thuật sẽ được coi là thành công nếu như cây mà Bob vẽ giống hệt với cây mà khán giả đã vẽ ban đầu.

Vì giới hạn kích thước của bảng, cây mà khán giả vẽ luôn đảm bảo có bậc tối đa nhỏ hơn hoặc bằng $8$ và số đỉnh tối đa có cùng bậc nhỏ hơn hoặc bằng $8$ $^\dagger$. Trong trò ảo thuật này, cây sẽ được mô phỏng dưới dạng một danh sách kề, mỗi đỉnh lưu trữ tất cả các con kề với đỉnh đó. Gốc của cây là đỉnh duy nhất không nằm trong danh sách kề của bất kỳ đỉnh nào.

Trò ảo thuật sẽ khiến mọi người càng bất ngờ nếu như giá trị lớn nhất mà Alice viết trên các lá bài càng nhỏ.

**Yêu cầu:** Hãy viết một chương trình mô phỏng lại trò ảo thuật của Alice và Bob.

$\dagger$: Trong cây, một đỉnh có bậc là $k$ nếu trên đường đi ngắn nhất từ gốc đến đỉnh đó có đúng $k$ cạnh. Bậc tối đa của cây được coi là bậc tối đa của các đỉnh trên cây đó.

## Chi tiết cài đặt

Bạn cần cài đặt hai hàm sau:

vector<int> solveAlice(vector<vector<int>> adj);

- $adj$ là một `vector<vector<int>>` mô phỏng ma trận kề của cây mà khán giả đã vẽ. Ma trận kề đảm bảo:
- $N=|adj|$
- Các đỉnh trên cây được đánh số từ $0$ đến $N-1$
- Mỗi phần tử $adj_i$ ($0\le i\le N-1$) là một `vector<int>` lưu tất cả các **đỉnh con** kề với đỉnh $i$ trên cây mà khán giả đã vẽ
- Giá trị duy nhất không xuất hiện trên các mảng $adj_i$ là gốc của cây.
- Đảm bảo $\sum_{|adj_i|}=N-1$
- Hàm này cần trả về một `vector<int>` tương ứng với các số nguyên dương Alice đánh trên các lá bài.

vector<vector<int>> solveBob(vector<int> S);

- $S$ là một `vector<int>` mô phỏng giá trị được viết trên các lá bài của Alice. Các giá trị này có thể được sắp xếp lại theo một thứ tự bất kỳ, không nhất thiết phải theo thứ tự các giá trị xuất hiện trên mảng mà Alice đã trả về.
- Hàm này cần trả về một `vector<vector<int>>` mô phỏng ma trận kề của cây mà Bob vẽ. Ma trận kề này cần mô phỏng cây y hệt so với cây mà khán giả đã vẽ. Cụ thể:
- Lá bài Bob chọn là gốc cũng phải là lá bài mà Alice đã chọn là gốc.
- Các cạnh nối giữa các cặp lá bài trên cây của Bob cũng phải là các cạnh nối giữa các cặp lá bài trên cây của khán giả đã vẽ.

**Lưu ý:**
- Chương trình sẽ gọi hai hàm liên tục $T$ lần, mỗi lần gọi tương ứng với một trường hợp thử nghiệm. Với mỗi trường hợp thử nghiệm, hàm `solveAlice()` luôn gọi trước hàm `solveBob()`.
- Chương trình của bạn cần phải khai báo thư viện `"magicianlib.h"` ở đầu.
- Trong chương trình của bạn, bạn được phép khai báo và gọi các hàm khác, nhưng không được phép chứa hàm `main()`.
- Hai hàm `solveAlice()` và `solveBob()` được thực hiện trên hai chương trình hoàn toàn độc lập.
- *Trong đề không nói gì về việc trình chấm có thích ứng hay không (nếu mọi người có thì cho em xin thông tin này với ạ).*

## Ràng buộc

- $T\le 100$
- $N\le 32$
- Cấu trúc của cây luôn đảm bảo bậc tối đa của cây nhỏ hơn hoặc bằng $8$ và số đỉnh tối đa có cùng bậc nhỏ hơn hoặc bằng $8$

## Subtask

- Subtask $1$ ($10$ điểm): $N\le 9$, cây mà khán giả vẽ luôn đảm bảo là một đường thẳng
- Subtask $2$ ($90$ điểm): Không có ràng buộc gì thêm

## Cách tính điểm

Gọi $M$ là số nguyên dương lớn nhất được viết trên các lá bài của Alice. Khi đó điểm của bạn được tính theo công thức như sau:

| Giá trị $M$ |Phần trăm số điểm|
|---------------|-----------------|
| $M\le 56$ | $100\%$ |
| $M=57$ | $80\%$ |
|$58\le M\le 88$| $(176-2M)\%$ |
| $M\ge 88$ | $0\%$ |

Điểm của một subtask bằng phần trăm điểm tối thiểu của một test trong subtask đó nhân với số điểm tối đa của subtask.