Chọn ĐT HSG QG Đà Nẵng 2024 Ngày 2

Tí có một đồ thị \(G\) vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Ta gọi một đỉnh thuộc đồ thị là cô đơn nếu nó chỉ có thể đến được không quá 1 đỉnh khác nó. Hai đỉnh \(u, v\) được gọi là đến được nhau nếu tồn tại một dãy các đỉnh \(v_1 = u, v_2, \dots, v_k = v\), sao cho \(\forall 1 \le i < k\) thì cạnh \((v_i, v_{i+1})\) thuộc đồ thị.

Ta có \(G(l, r)\) là đồ thị \(G\) nhưng chỉ giữ lại các đỉnh có chỉ số trong đoạn \([l, r]\) và các cạnh nối giữa các đỉnh trong đoạn \([l, r]\); độ cô đơn \(f(l, r)\) sẽ là số lượng đỉnh cô đơn có trong đồ thị \(G(l, r)\). Nhiệm vụ của Tí là tính tổng:

Input

• Dữ liệu vào từ file văn bản LGR.INP:
  • Dòng đầu tiên chứa hai số nguyên \(n\) (\(1 \le n \le 10^5\)), \(m\) (\(0 \le m \le 2 \cdot 10^5\)).
  • \(m\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(u_i, v_i\) (\(1 \le u_i, v_i \le n\)) mô tả hai đỉnh nối bởi cạnh thứ \(i\). Dữ liệu đảm bảo \(\forall i \neq j: u_i \neq u_j\) hoặc \(v_i \neq v_j\).

Output

• Ghi ra file văn bản LGR.OUT:
  • Ghi kết quả trên một dòng, là tổng độ cô đơn của tất cả \(G(l, r)\).

Example

5 3
2 4
1 2
2 3

18

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 300, m \le 600\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 2000, m \le 4000\).
• Subtask \(3\) (\(25\%\) số điểm): \(f(1, n) \ge n - 3\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Cho dãy \(a\) gồm \(n\) phần tử, được đánh số từ \(1\) tới \(n\). Ta gọi \(f(l, r)\) là số lớn nhất có dạng \(2^x\) sao cho tổng của các số \(a_l, a_{l+1}, \dots, a_r\) chia hết cho \(2^x\). Nhiệm vụ của bạn là tính tổng của tất cả các \(f(l, r)\) với \(1 \le l \le r \le n\).

Input

• Dữ liệu vào từ file văn bản VARR.INP:
  • Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 2 \times 10^5\)) tương ứng là độ dài của dãy \(a\).
  • Dòng thứ hai chứa \(n\) số nguyên mô tả dãy \(a\), số nguyên thứ \(i\) là giá trị của \(a_i\) (\(1 \le a_i \le 10^6\), \(\sum_{i=1}^{n} a_i \le 10^6\)).

Output

• Ghi ra file văn bản VARR.OUT:
  • Ghi kết quả trên một dòng, là kết quả của bài toán sau khi lấy phần dư khi chia cho \(10^9 + 7\).

Example

3
1 2 3

8

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 200\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 5000\).
• Subtask \(3\) (\(25\%\) số điểm): \(\sum_{i=1}^{n} a_i \le 2 \times 10^5\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Cho cây gồm \(n\) đỉnh, mỗi cạnh của cây có thể được tô một màu nào đó. Một đường đi đơn trên cây là đường đi không lặp lại cạnh, một đường đi đơn gọi là xấu khi và chỉ khi các cạnh trên đường đi đó có màu phân biệt. Một cây được gọi là xấu khi và chỉ khi tồn tại ít nhất một đường đi đơn độ dài \(k\) là xấu. Ta sẽ tìm cách tô màu các cạnh của cây, sao cho cây không là một cây xấu, độ đẹp của cây là số lượng màu khác nhau ta sử dụng để tô các cạnh. Hãy tìm cách tô sao cho độ đẹp là lớn nhất.

Input

• Dòng đầu tiên chứa lần lượt hai số nguyên \(n, k\) (\(1 \le k \le n \le 10^5, k \le 30\)) tương ứng là số đỉnh của cây đồ thị và số \(k\) như mô tả bài toán.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) (\(1 \le u, v \le n\)) tương ứng với hai cạnh nối cặp đỉnh \((u, v)\) trên cây.

Output

• Ghi ra trên một dòng là độ đẹp lớn nhất của cây.

Example

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

3

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 30, k \le 10\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 5 \times 10^4\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.