LQDOJ Cup 2024 - Round #9

Một ngôi làng có \(n\) ngôi nhà và \(n\) con đường nối các ngôi nhà với nhau và đảm bảo các ngôi nhà liên thông với nhau.

Sắp đến mùa lễ hội nên trưởng làng muốn tổ chức nhiều lễ hội nhất có thể,một lễ hội có thể tổ chức trên một con đường và \(2\) ngôi nhà là \(2\) đầu của con đường này.Và cần đảm bảo mỗi ngôi nhà chỉ được tổ chức tối đa một lễ hội.

Hãy giúp trưởng làng tính xem có tối đa bao nhiêu lễ hội có thể tổ chức.

Đảm bảo \(2\) ngôi nhà chỉ được nối với nhau bởi tối đa một con đường.

Input

• Dòng đầu gồm một số nguyên dương \(n\) (\(3 \le n \le 5 \times 10^5\)) --- số ngôi nhà.
• \(n\) dòng tiếp theo mỗi dòng gồm \(2\) số nguyên dương \(u,v\)(\(1 \le u,v \le n\),\(u \neq v\)) --- mô tả các con đường.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(16\%\) số điểm): mỗi ngôi nhà có tối đa \(2\) đường đi nối đến nó.
• Subtask \(2\) (\(26\%\) số điểm): \(n \le 20\).
• Subtask \(3\) (\(27\%\) số điểm): \(n \le 5 \times 10^3\).
• Subtask \(4\) (\(31\%\) số điểm): không có ràng buộc gì thêm.

Example

5
1 2
2 3
3 4
4 1
1 5

2

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

3

Cho một rừng cây gồm \(n\) đỉnh và \(m\) cạnh.

Có \(q\) câu hỏi có dạng \(x\) \(y\) mang ý nghĩa sau:

• Gọi \(X\) là tập đỉnh thuộc thành phần liên thông chứa \(x\).
• Gọi \(Y\) là tập đỉnh thuộc thành phần liên thông chứa \(y\).
• Có \(|X| \times |Y|\) cách để thêm một cạnh vào cây sao cho \(x\) và \(y\) thuộc cùng một thành phần liên thông. Chắc chắn thành phần liên thông mới được tạo ra là một cây.
• Hãy tính tổng đường kính của cây được tạo ra trong \(|X| \times |Y|\) trường hợp đó.
• Trong tình huống ngay từ đầu \(x\) và \(y\) thuộc cùng một thành phần liên thông thì xem như đáp án bằng \(0\).
• Lưu ý rằng các câu hỏi là các tình huống giả định và không thêm cạnh vào rừng.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(n, m\) và \(q\) \((1 \leq n, m, q \leq 10^{6}; m \leq n - 1)\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u\) và \(v\) \((1 \leq u, v \leq n)\) thể hiện một cạnh của rừng.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(x\) và \(y\) \((1 \leq x, y \leq n)\) thể hiện một câu hỏi.

Output

• Gồm \(q\) dòng, dòng thứ \(i\) chứa một số nguyên thể hiện kết quả của truy vấn thứ \(i\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n, m, q \leq 100\).
• Subtask \(2\) (\(17\%\) số điểm): \(m = n - 1\).
• Subtask \(3\) (\(20\%\) số điểm): \(m = n - 2\).
• Subtask \(4\) (\(23\%\) số điểm): \(|u - v| \leq 1\).
• Subtask \(5\) (\(25\%\) số điểm): không có giới hạn gì thêm.

Examples

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

0
8
8
1

Trong một lần đi du lịch, Vũ vô tình bị lạc tại một hòn đảo hoang. Diện tích đảo là một hình chữ nhật \(n \times m\), biểu diễn như một ma trận. Tại mỗi ô trong đảo là một vật cản, một kho báu có giá trị nhất định, một quả bom, hoặc một ô trống. Bạn cũng biết được ô mà Vũ đang đứng. Nhưng rất xui cho anh bởi vì 1 tuần sau cơn bão \(\textbf{yagi}\) sẽ quét qua hòn đảo này, khi bão vào sẽ làm dâng nước biển lên vì vậy Vũ cần phải xây một tường chắn bắt đầu từ vị trí đang đứng của anh ta. Tiếp theo anh ta sẽ được quyền chọn 1 trong 4 ô kề cạnh với ô hiện tại và di chuyển qua đó xây bức tường tại ô đó và khi đứng trên ô nào phải bắt buộc phải xây tại ô đó (có thể xây đè lên ô đã xây). Và cuối cùng là quay lại vị trí anh ta đang đứng (tạo thành một đường đi khép kín). Lưu ý khi xây bức tường chỉ xây tại vị trí từ tâm của ô hiện tại sang tâm của ô tiếp theo (xem ví dụ để hiểu hơn)

• Vũ không được đi ra khỏi hòn đảo (biên của hình chữ nhật).
• Vũ không được phép đi qua ô mà có vật cản, bom và kho báu.
• Vũ được phép đi qua những ô đã qua.
• Khi tạo thành đường khép kín quả bom không được phép nằm trong đó. Hay nói cách khác khi nước dâng lên thì mọi quả bom đều phải nằm ở dưới nước và không được nằm trong bức tường mình vừa xây.

Nhiệm vụ của Vũ:

• Khi nước dâng lên, Vũ sẽ nhận được số vàng ở trong các ô kho báu khi nó nằm hoàn toàn bên trong bức tưởng chắn hay là đường khép kín(không tính trên cạnh hay trên bức tường);
• Gọi giá trị kho báu mà Vũ nhận được là \(p\) và số số lượt đi từ ô này sang ô khác là \(d\).
• Vũ phải xây sao cho giá trị \(p - d\) là lớn nhất.

Được biết tổng số ô chứa bom và ô chứa kho báu không vượt quá 8.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1\leq n,m \leq 20)\) tương ứng với chiều dài và chiều rộng của đảo.
• Tiếp theo là \(n\) dòng với mỗi dòng là \(m\) kí tự với kí tự thứ \((i, j)\) là:
  • Kí tự B cho biết vị trí đó có bom.
  • Kí tự # cho biết vị trí đó có vật cản.
  • Kí tự . cho biết vị trí đó có là ô trống.
  • Kí tự S cho biết vị trí đó Vũ đang đứng và đó chắc chắn là ô trống.
  • Cuối cùng, kí tự từ 1 đến 9 chính là ô kho báu có thứ tự tương ứng, các số trong bảng luôn là phân biệt
  • Chú ý tổng số ô chứa bom và ô chứa kho báu không vượt quá 8.
• Dòng cuối cùng gồm các số \(a_i\) với \((-200 \le a_i \le 200)\) tương ứng với giá trị của kho báu thứ i.

Output

• Một số duy nhất là giá trị lớn nhất mà Vũ nhận được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \times m \le 20\)
• Subtask \(2\) (\(15\%\) số điểm): cách đi tối ưu là luôn tạo thành duy nhất một hình chữ nhật.
• Subtask \(3\) (\(20\%\) số điểm): trên bản đồ chỉ tồn tại duy nhất một ô kho báu.
• Subtask \(4\) (\(15\%\) số điểm): bản đồ không chứa bom.
• Subtask \(5\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Examples

4 4 
2...
.1B.
..##
.S..
100 -50

0

4 5
2.#..
.....
..13.
.S...
100 -50 34

124

10 11
.3.....#...
...........
....6#..B..
#..........
...#.B.....
.S.......5.
........4..
#...#..2...
...........
..........1
2 56 46 -33 29 27

43