# Đề Chọn ĐT HSG 10 + 11 - THPT chuyên Lê Quý Đôn (BRVT) - 2025: Editorial

Sau đây là lời giải của kỳ thi **Chọn Đội tuyển Học sinh giỏi lớp 10 + 11 trường THPT chuyên Lê Quý Đôn tỉnh Bà Rịa - Vũng Tàu năm học 2024 - 2025**.

Bạn đọc có thể nộp chấm thử [**tại đây**]( https://codeforces.com/contestInvitation/003a5bbb3c57681cc6d0a92f81b918d5eae7373e) và xem đề gốc [**tại đây**](https://drive.google.com/file/d/1LTPmK12XSV502Fh7Yt-NmnDCJAyAi2N2/view?usp=drive_link)!

[toc]

## Bài 1: Tommy (4 điểm)

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

Cho dãy $n$ số nguyên dương $X_1,X_2,\dots,X_n$ và $m$ truy vấn, mỗi truy vấn được cho bởi $2$ số nguyên $L_i,R_i$ $\left(X_i \le 10^7, \; 1 \le L_i \le R_i \le 10^9 \right)$.

$f(p)$ là số lượng số $X_i$ là bội của $p$.

**Yêu cầu:** Với mỗi truy vấn $L_i,R_i$, tính $\sum_{p \in S \left( L_i,R_i \right)}^{f \left( p \right)}$ với $S \left( L_i,R_i \right)$ là tập các số nguyên tố trong đoạn $\left[L_i,R_i\right]$.

**Subtasks:**
- $30\%$ số điểm: $0 \lt n,m \le 2 \cdot 10^3, \; 2 \le L_i \le R_i \le 10^3$.
- $30\%$ số điểm: $0 \lt n,m \le 2 \cdot 10^3, \; 2 \le L_i \le R_i \le 10^6$.
- $40\%$ số điểm: Không có ràng buộc gì thêm.

### Subtask 1:
>[!Important] Định nghĩa:
>- $prime_i$ thể hiện ==tính nguyên tố== của $i$.
> - Nếu $i$ là số nguyên tố, $prime_i = 1$ .
> - Nếu $i$ không phải số nguyên tố, $prime_i = 0$.
>- $sum_i = \sum_{p \in S \left(1, i \right)}^{f \left( p \right)}$ là ==tổng $f(p)$== với $p$ là các ==số nguyên tố trong đoạn $\left[ 1, i \right]$==:
> - Nếu $prime_i = 0$, $sum_i = sum_{i-1}$.
> - Nếu $prime_i = 1$, $sum_i = sum_{i-1} + f \left( i \right)$.

Trước tiên, cần tính trước ==$prime_i$ $\forall$ $i \in \left[1,10^3\right]$==. Vì giới hạn nhỏ, ta duyệt qua tất cả $i$ và kiểm tra tính nguyên tố của $i$ bằng cách duyệt đến $\sqrt i$.

Sau đó, với mỗi số $X_i$ ta duyệt qua tất cả ước $d$ của $X_i$, nếu $prime_d = 1$ (tức $d$ là số nguyên tố) thì tăng $f_d$ lên $1$ đơn vị.

Cuối cùng, tính $sum_i$ theo công thức dựa vào $f_i$ đã cho ở trên.

Đáp án của truy vấn thứ $i$ là ==$sum_{R_i} - sum_{L_i-1}$==.

Độ phức tạp thời gian: $O \left(n \cdot \sqrt X\right)$ với $X = \max \left( X_i \right) = 10^7$.

:::success
:::spoiler Code

#include<bits/stdc++.h>
using namespace std;

const int N = 2e3;
int n, m, X[N+1], prime[N+1], f[N+1], sum[N+1];

bool check_prime(int x) {
	if (x < 2) {
		return 0;
	}

    int t = sqrt(x);
    for (int i = 2; i <= t; i++) {
        if (x % i == 0) {
            return 0;
        }
    }
    
    return 1;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> X[i];
    }
    
    for (int i = 1; i <= N; i++) {
        prime[i] = check_prime(i);
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j*j <= X[i]; j++) {
            if (X[i] % j == 0) {
                if (j <= N && prime[j]) {
                    f[j]++;
                }
                if (X[i]/j <= N && X[i]/j != j && prime[X[i]/j]) {
                    f[X[i] / j]++;
                }
            }
        }
    }
    
    for (int i = 1; i <= N; i++) {
        sum[i] = sum[i-1];
        if (prime[i]) {
            sum[i] += f[i];
        }
    }
    
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        cout << sum[r] - sum[l-1] << '\n';
    }
    
    return 0;
}

:::

### Subtask 2:
Ý tưởng tương tự như **subtask 1**, nhưng cần cải tiến quá trình ==tính trước mảng $prime$== bằng [**sàng nguyên tố Eratosthenes**](https://blog.28tech.com.vn/sang-so-nguyen-to) vì khi này $L_i,R_i \le 10^6$, tương ứng với $p \le 10^6$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e3, V = 1e6;
int n, m, X[N+1], prime[V+1];
long long sum[V+1], f[V+1];

void sieve() {
    fill(prime, prime + 1 + V, 1);
    prime[0] = prime[1] = 0;
    
    for (int i = 2; i*i <= V; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= V; j += i) {
                prime[j] = false;
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> X[i];
    }
    
    sieve();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j*j <= X[i]; j++) {
            if (X[i] % j == 0) {
                if (j <= V && prime[j]) {
                    f[j]++;
                }
                if (X[i] / j <= V && X[i] / j != j && prime[X[i] / j]) {
                    f[X[i] / j]++;
                }
            }
        }
    }
    
    for (int i = 1; i <= V; i++) {
        sum[i] = sum[i-1];
        if (prime[i]) {
            sum[i] += f[i];
        }
    }
    
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        cout << sum[r] - sum[l-1] << '\n';
    }

    return 0;
}

:::

### Subtask 3:

>[!Tip] **Cải tiến 1**:
>Vì $X_i \le 10^7$ nên $f_i = 0$ nếu $i \gt 10^7$. Khi này, ta chỉ việc tính $sum_i$ với $i \le 10^7$.

>[!Tip] **Cải tiến 2**:
>Để tính $f_i$ ta có thể áp dụng tư tưởng của **sàng nguyên nguyên tố Eratosthenes**. Ta thực hiện duyệt qua ==tất cả các bội của mọi số nguyên tố $i$==.
>
> Độ phức tạp thời gian của thuật toán trên nếu duyệt đến $n$ là $O\left(n \log \log {n}\right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5, V = 1e7;
int n, m, X[N+1], prime[V+1], sum[V+1], f[V+1];

void sieve() {
    fill(prime, prime + 1 + V, 1);
    prime[0] = prime[1] = 0;
    
    for (int i = 2; i * i <= V; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= V; j += i) {
                prime[j] = 0;
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> X[i];
    }
    
    sieve();
    for (int i = 1; i <= n; i++) {
        f[X[i]]++;
    }
    
    for (int i = 1; i <= V; i++) {
        if (prime[i]) {
            for (int j = 2*i; j <= V; j += i) {
                f[i] += f[j];
            }
        }
    }
    
    for (int i = 1; i <= V; i++) {
        sum[i] = sum[i-1];
        if (prime[i]) {
            sum[i] += f[i];
        }
    }
    
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        
        if (l > 1e7) {
            cout << 0 << '\n';
            continue;
        }
        
        r = min(r, V);
        
        cout << sum[r] - sum[l-1] << '\n';
    }
    
    return 0;
}

:::

## Bài 2: Đoạn đường dài nhất (5 điểm)

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

Có $n$ tòa nhà nằm dọc một bên của con đường. Tòa nhà thứ $i$ tính từ đầu đường có độ cao trung bình là $A_i$ $\left( 0 \le A_i \le 10^9 \right)$.

**Yêu cầu:** Tìm đoạn đường dài nhất chứa các tòa nhà liên tiếp sao cho chúng có độ cao trung bình đúng bằng $k$ $\left( 0 \le k \le 10^9 \right)$.

**Subtasks:**
- $40\%$ số điểm: $\left( 1 \le n \le 500 \right)$.
- $30\%$ số điểm: $1 \le n \le 5 \cdot 10^3$.
- $30\%$ số điểm: $1 \le n \le 10^5$.

**Tổng quát bài toán:** Tìm đoạn con dài nhất của mảng sao cho ==trung bình cộng của đoạn con đó bằng $k$==.

### Subtask 1:

Duyệt hai vòng lặp với biến $i, j \left( i \le j \right)$ để cố định biên trái và biên phải của một đoạn (tức là duyệt qua ==tất cả các đoạn con $\left[ i, j \right]$== của mảng).

Với mỗi đoạn $\left[ i, j \right]$ tương ứng, lại duyệt thêm một vòng lặp để tính tổng các phần tử.

Đoạn $\left[ i, j \right]$ có trung bình cộng bằng $k$ khi và chỉ khi:
$$
\frac {A_i + A_{i+1} + \dots + A_j}{j-i+1} = k
$$

Độ phức tạp thời gian: $O \left( n^3 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 500;
int n, k, A[N+1], resLen, resPos;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> X[i];
    }
    
    //Duyệt qua mọi đoạn [i, j]
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            //Tính tổng đoạn
            long long sum = 0;
            for (int k = i; k <= j; k++) {
                sum += A[k];
            }
            
            //Cập nhật kết quả
            int len = j-i+1;
            if (sum % len == 0 && sum / len == k) {
                if (resLen < len) {
                    resLen = len;
                    resPos = i;
                }
                else if (resLen == len) {
                    //Ưu tiên lấy điểm xuất phát nhỏ nhất
                    resPos = min(resPos, i);
                }
            }
        }
    }

    cout << resPos;

    //Nếu tồn tại đáp án
    if (resPos != 0) {
        cout << " " << resLen;
    }

    return 0;
}

:::

### Subtask 2:

Ý tưởng tương tự với **subtask 1**. Tuy nhiên cần cải tiến thao tác kiểm tra một đoạn $\left[ i, j \right]$ có trung bình cộng bằng $k$ hay không.

Nhận thấy chỉ cần tổng đoạn để kiểm tra, ta có thể sử dụng ==mảng cộng dồn (prefix sum)== để tính nhanh tổng của mỗi đoạn $\left[ i, j \right]$ trong thời gian $O(1)$.

Độ phức tạp thời gian: $O \left( n^2 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 500;
int n, k, A[N+1], S[N+1], resLen, resPos;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> X[i];
        S[i] = S[i-1] + X[i];
    }
    
    //Duyệt qua mọi đoạn [i, j]
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            //Tính tổng đoạn
            long long sum = S[j] - S[i-1];
            
            //Cập nhật kết quả
            int len = j-i+1;
            if (sum % len == 0 && sum / len == k) {
                if (resLen < len) {
                    resLen = len;
                    resPos = i;
                }
                else if (resLen == len) {
                    //Ưu tiên lấy điểm xuất phát nhỏ nhất
                    resPos = min(resPos, i);
                }
            }
        }
    }

    cout << resPos;

    //Nếu tồn tại đáp án
    if (resPos != 0) {
        cout << " " << resLen;
    }

    return 0;
}

:::

### Subtask 3:

>[!Important] Phân tích bài toán
>Đoạn $\left[ i, j \right]$ có trung bình cộng là $k$
>$$
>\begin{flalign}
>&\Leftrightarrow \frac {A_i + A_{i+1} + \dots + A_j}{j-i+1} = k \\
>&\Leftrightarrow A_i + A_{i+1} + \dots + A_j = k \cdot \left( j - i + 1 \right) \\
>&\Leftrightarrow \left( A_i - k \right) + \left( A_{i+1} - k \right) + \dots + \left( A_j - k \right) = 0
>\end{flalign}
>$$
>Như vậy, ta đã đơn giản hóa bài toán trở thành: ==Tìm đoạn con dài nhất có tổng bằng $0$==

Bài toán trên có thể được giải như sau:
- Cố định vị trí $j$.
- Tìm $i$ nhỏ nhất sao cho ==$\left( A_i - k \right) + \left( A_{i+1} - k \right) + \dots + \left( A_j - k \right) = 0$==,
hay ==$S_j - S_{i-1} = 0$== với $S_i = \left( A_1 - k \right) + \left( A_2 - k \right) + \dots + \left( A_i - k \right)$.

Sử dụng kiểu dữ liệu **map**, khai báo $mn$ với $mn_x$ là $i$ nhỏ nhất thỏa $S_i = x$. Như vậy, ở mỗi vị trí $j$ thì đoạn $\left[ mn_{S_j} + 1, i \right]$ là đoạn con dài nhất kết thúc tại $i$ và thỏa điều kiện đề bài.

Độ phức tạp thời gian: $O \left( n \log n \right)$.
> Các thao tác trên **map** có độ phức tạp thời gian là $O \left( \log n \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
int n, k, resLen, resPos;
map<long long, int> mn;
long long sum;

int main() {
    cin >> n >> k;
    mn[0] = 0;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        x -= k;
        sum += x;

        //Nếu tồn tại giá trị sum trong mn
        if (mn.count(sum)) {
            int len = i - mn[sum];
            if (resLen < len) {
                resLen = len;
                resPos = mn[sum] + 1;
            }
            else if (resLen == len) {
                //Ưu tiên lấy điểm xuất phát nhỏ nhất
                resPos = min(resPos, mn[sum] + 1);
            }
        }
        else {
            mn[sum] = i;
        }
    }

    cout << resPos;

    //Nếu tồn tại đáp án
    if (resPos != 0) {
        cout << " " << resLen;
    }

    return 0;
}

:::

## Bài 3: Cắt cành (6 điểm)

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

Cho một cây gồm $n$ trái ớt được nối với nhau bởi $n-1$ cạnh.

**Yêu cầu:** Tìm cách cắt cắt $2$ cành cây bất kì để được $3$ đùm ớt thỏa mãn độ chênh lệch giữa đùm có nhiều ớt nhất và ít nhất là nhỏ nhất.

**Subtasks:**
- $25\%$ số điểm: $3 \le n \le 200$.
- $250\%$ số điểm: $3 \le n \le 2000$.
- $50\%$ số điểm: $3 \le n \le 200000$.

**Tổng quát bài toán:** Tìm cách ==xóa $2$ cạnh bất kỳ trên một đồ thị dạng cây để được $3$ thành phần liên thông có kích thước *gần bằng nhau* nhất== (nghĩa là chênh lệch giữa kích thước của thành phần liên thông lớn nhất và kích thước của thành phần liên thông nhỏ nhất là nhỏ nhất).

### Subtask 1:

>[!Tip] Nhận xét:
> Khi thay đổi gốc của cây, các cách cắt cành vẫn giữ nguyên (nghĩa là với một cách cắt cành bất kỳ ở gốc $i$, ta luôn tìm được cách cắt cho ra kết quả tương tự khi cây nhận gốc $j \not = i$). Do đó, ta chỉ cần xét một đỉnh bất kỳ của cây làm gốc.
>
> **Lưu ý:** Trong editorial này, ==đỉnh $1$ được lựa chọn làm gốc==.

Duyệt hai vòng lặp để thử ==tất cả các cách cắt hai cạnh $i, j$ $\left( i \not = j \right)$==.

Với mỗi cặp cạnh $\left( u_i, v_i \right)$ và $\left( u_j, v_j \right)$, ta thực hiện DFS từ các đỉnh $u_i, v_i, u_j, v_j$ mà ==không được đi qua hai cạnh trên== để tính kích thước của các thành phần liên thông bị tách ra.

Trong số $4$ kết quả trả về tương ứng với kết quả của $4$ lần DFS, có $2$ kết quả là từ cùng một thành phần liên thông, nhưng dễ thấy điều này không ảnh hưởng đến kết quả.

**Kết quả:** $\min \left( \max \left( sz_{u_i}, sz_{v_i}, sz_{u_j}, sz_{u_j} \right) - \min \left( sz_{u_i}, sz_{v_i}, sz_{u_j}, sz_{u_j} \right) \right)$ $\forall$ $1 \le i \lt j \lt n$.

**Độ phức tạp thời gian:**
- Duyệt qua mọi cặp cạnh: $O \left( n^2 \right)$.
- DFS: $O \left( n + \left(n - 1 \right) \right) = O \left( 2 \cdot n - 1 \right)$
- **Tổng:** $O \left( n^2 \cdot \left( 2 \cdot n - 1 \right) \right) \approx O \left( n^3 \right)$

:::success
:::spoiler Code

:::

### Subtask 2:

Ý tưởng tương tự như **subtask 1**, tuy nhiên cần cải tiến quá trình ==tính kích thước của các thành phần liên thông bị tách ra==.

>[!Important]
>Định nghĩa $sz_i$ là ==kích thước của cây con gốc $i$==.
>Giả sử hai cạnh bị cắt là $\left( u_i, v_i \right)$ và $\left( u_j, v_j \right)$.
>Không mất tính tổng quát, cho ==$u_i$ là cha của $v_i$==, và ==$u_j$ là cha của $v_j$==.

Xem xét kỹ, có thể thấy bài toán chỉ có hai trường hợp:

#### ==TRƯỜNG HỢP 1:== Hai cạnh bị cắt ==nằm trong cùng một nhánh== (tức là một cạnh sẽ thuộc cây con của một đỉnh trong cạnh còn lại).

- **Nếu $u_j$ thuộc cây con gốc $v_i$**, kích thước các thành phần liên thông là:

$$
sz_{v_j}, sz_{v_i} - sz_{v_j}, n - sz_{v_i}
$$

- Ngược lại, **nếu $u_i$ thuộc cây con gốc $v_j$**, kích thước các thành phần liên thông là:

$$
sz_{v_i}, sz_{v_j} - sz_{v_i}, n - sz_{v_j}
$$

**Ví dụ:**

> Cắt cạnh $\left( 3, 5 \right)$ và cạnh $\left( 7, 9 \right)$.
> Đỉnh $7$ nằm trong cây con gốc là đỉnh $5$.

Kích thước các thành phần liên thông là:

$$
sz_9 = 1, sz_5 - sz_9 = 5 - 1 = 4, n - sz_5 = 9 - 5 = 4
$$

#### ==TRƯỜNG HỢP 2:== Hai cạnh bị cắt nằm ở ==hai nhánh khác nhau==

Kích thước các thành phần liên thông là:

$$
sz_{v_i}, sz_{v_j}, n - sz_{v_i} - sz_{v_j}
$$

**Ví dụ:**

> Cắt cạnh $\left( 3, 2 \right)$ và cạnh $\left( 5, 7 \right)$.

Kích thước các thành phần liên thông là:

$$
sz_2 = 1, sz_7 = 3, n - sz_2 - sz_7 = 9 - 1 - 3 = 5
$$

#### ==HƯỚNG GIẢI:==
Có thể áp dụng ==Quy hoạch động trên cây== và ==Euler Tour== như sau:
- Quy hoạch động để tính $sz_i$ $\left( 1 \le i \le n \right)$.
- Euler Tour để xác định nhanh một đỉnh có thuộc cây con của đỉnh khác hay không.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
int n, cnt, res = INT_MAX;
int sz[N+5], in[N+5], out[N+5];
vector<int> adj[N+5];

void dfs(int u, int root) {
    sz[u] = 1;
    in[u] = ++cnt;
    for (int v : adj[u]) {
        if (v == root) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
    
    out[u] = cnt;
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    dfs(1, -1);

    for (int i = 2; i <= n; i++){
        for (int j = 2; j < i; j++){
            int tmp1, tmp2, tmp3;
            int x = i, y= j;
            
            //Luôn đảm bảo y là con của x
            if (sz[x] < sz[y]) swap(x, y); 
            
            if (in[y] >= in[x] && in[y] <= out[x]) {
                //Nếu y là con của x:
                tmp1 = sz[y];
                tmp2 = sz[x] - sz[y];
                tmp3 = n - sz[x];
            }
            else {
                // nếu y không phải là con của x:
                tmp1 = sz[x];
                tmp2 = sz[y];
                tmp3 = n - sz[x] - sz[y];
            }
            
            res = min(res, max({abs(tmp1 - tmp2), abs(tmp1 - tmp3), abs(tmp2 - tmp3)}));
        }
    }

    cout << res;
}

int main() {
    solve();
    return 0;
}

:::

### Subtask 3:

Ta cẩn thay đổi hướng tiếp cận để giải được **subtask 3**. Với $n \le 2 \cdot 10^5$, việc thử tất cả các cặp cạnh là bất khả thi. Do đó, ta cố định cạnh $\left( u_i, v_i \right)$ và tìm cạnh $\left( v_i, v_j \right)$ cho đáp án tối ưu nhất.

Ta xét hai trường hợp tương tự như **subtask 2**:

#### ==TRƯỜNG HỢP 1:== Cạnh $\left( u_j, v_j \right)$ nằm cùng nhánh và không nằm trong cây con gốc $v_i$

Ta cần làm cho các kích thước sau *gần bằng nhau* nhất có thể:

$$
sz_{v_i}, sz_{v_j} - sz_{v_i}, n - sz_{v_j}
$$

Nhận thấy $sz_{v_i}$ đã cố định,còn $sz_{v_j}$ trong hai biểu thức còn lại thì ngược dấu với nhau, dẫn đến việc hai giá trị sẽ có xu hướng tăng hoặc giảm ngược nhau. Có nghĩa là, để các kích thước trên *gần bằng nhau*, ta sẽ tìm cách cho $sz_{v_j} - sz_{v_i}$ gần bằng $n - sz_{v_j}$ nhất.

>[!Tip] Chốt lại
> Tìm cạnh $\left( u_j, v_j \right)$ sao cho $\left| sz_{v_j} - sz_{v_i} - n + sz_{v_j} \right| = \left| 2 \cdot sz_{v_j} - (sz_{v_i} + n) \right|$.
> $\Leftrightarrow$ $j$ để $sz_{v_j}$ gần bằng $\frac {sz_{v_i} + n}{2}$ nhất.

#### ==TRƯỜNG HỢP 2:== Cạnh $\left( u_j, v_j \right)$ nằm khác nhánh

Ta cần làm cho các kích thước sau *gần bằng nhau* nhất có thể:

$$
sz_{v_i}, sz_{v_j}, n - sz_{v_i} - sz_{v_j}
$$

Tương tự TH1, để các kích thước trên *gần bằng nhau*, ta sẽ tìm cách cho $sz_{v_j}$ gần bằng $n - sz_{v_i} - sz_{v_j}$ nhất.

>[!Tip] Chốt lại
> Tìm cạnh $\left( u_j, v_j \right)$ sao cho $\left| sz_{v_j} - n + sz_{v_i} + sz_{v_j} \right| = \left| 2 \cdot sz_{v_j} - (n - sz_{v_i}) \right|$.
> $\Leftrightarrow$ $sz_{v_j}$ gần bằng $\frac {n - sz_{v_i}}{2}$ nhất.

#### ==CHỐT LẠI LÀ:==

Ta cần duy trì $2$ cấu trúc dữ liệu **set**:
- $stCur$: Các giá trị $sz_{v_j}$ ==đã đi qua trong nhánh đang xét==.
- $stPrv$: Các giá trị $sz_{v_j}$ ==trong những nhánh đã đi qua==

Khi duyệt DFS xong một nhánh và trả đệ quy, ta cần thực hiện thao tác `erase` trên $stCur$ và `insert` phần tử đó vào $stPrv$.

Tìm đáp án như hướng dẫn ở trên bằng lệnh `lower_bound`.

>[!Caution] Cảnh báo
> Hàm `lower_bound` thường cửa C++ khác với hàm `lower_bound` tích hợp trong cấu trúc dữ liệu **set**. Việc nhầm lẫn sẽ không sinh lỗi nhưng lại gây TLE!

Độ phức tạp thời gian: $O \left( n \log n \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;
int n, sz[N+1], res = INT_MAX;
vector<int> adj[N+1];

void init(int u, int p) {
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v != p) {
            init(v, u);
            sz[u] += sz[v];
        }
    }
}

set<int> stCur, stPrv;
void dfs(int u, int p) {
    //Case 1: u's ancestor
    if (!stCur.empty()) {
        auto posA = stCur.lower_bound((n + sz[u])/2);
        auto posB = posA;
        posB--;

        if (posA == stCur.end()) res = min(res, max({*posB - sz[u], sz[u], n - *posB}) - min({*posB - sz[u], sz[u], n - *posB}));
        else if (posA == stCur.begin()) res = min(res, max({*posA - sz[u], sz[u], n - *posA}) - min({*posA - sz[u], sz[u], n - *posA}));
        else {
            res = min(res, max({*posB - sz[u], sz[u], n - *posB}) - min({*posB - sz[u], sz[u], n - *posB}));
            res = min(res, max({*posA - sz[u], sz[u], n - *posA}) - min({*posA - sz[u], sz[u], n - *posA}));
        }
    }

    //Case 2: different branch
    if (!stPrv.empty()) {
        auto posA = stPrv.lower_bound((n - sz[u])/2);
        auto posB = posA;
        posB--;

        if (posA == stPrv.end()) res = min(res, max({*posB, sz[u], n - sz[u] - *posB}) - min({*posB, sz[u], n - sz[u] - *posB}));
        else if (posA == stPrv.begin()) res = min(res, max({*posA, sz[u], n - sz[u] - *posA}) - min({*posA, sz[u], n - sz[u] - *posA}));
        else {
            res = min(res, max({*posB, sz[u], n - sz[u] - *posB}) - min({*posB, sz[u], n - sz[u] - *posB}));
            res = min(res, max({*posA, sz[u], n - sz[u] - *posA}) - min({*posA, sz[u], n - sz[u] - *posA}));
        }
    }

    //Joining branch
    if (p != 0) {
        stCur.insert(sz[u]);
    }

    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }

    //Leaving branch
    if (p != 0) {
        stCur.erase(sz[u]);
        stPrv.insert(sz[u]);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n-1; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].pb(v);
        adj[v].pb(u);
    }

    init(1, 0);
    dfs(1, 0);
    cout << res;

    return 0;
}

:::

## Bài 4: Đa giác (5 điểm)

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

Cho $n$ tấm gỗ, tấm gỗ thứ $i$ có độ dài $l_i$ $\left(1 \le l_i \le n \le 5000 \right)$.
**Yêu cầu**: Đếm số cách xếp các tấm gỗ để tạo thành một đa giác lồi. Đáp án chia dư cho $10^9+7$.

**Subtasks:**
- $30\%$ số điểm: $0 \lt n \le 40$.
- $30\%$ số điểm: $0 \lt n \le 500$.
- $40\%$ số điểm: $0 \lt n \le 5000$.

>[!Tip] Đơn giản hóa bài toán
>:::info
>**Nhận xét 1**:
>Để $n$ cạnh có thể tạo thành đa giác thì tổng độ dài của $n-1$ cạnh bất kì phải lớn hơn cạnh còn lại. Điều này tương đương cạnh lớn nhất phải bé hơn tổng độ dài $n-1$ cạnh còn lại.
>:::
>
>:::info
>**Nhận xét 2**:
>Giả sử $l_1 \le l_2 \le \dots \le l_n$.
>Khi này, các cạnh $l_{i_1},l_{i_2},\dots,l_{i_k} \; \left(1 \le i_1 \lt i_2 \lt \dots \lt i_k \le n\right)$ sẽ tạo thành đa giác lồi khi và chỉ khi $l_{i_1}+l_{i_2}+\dots+l_{i_{k-1}} \gt l_{i_k}$.
>Do đó, ta chỉ việc sort lại mảng $l$ tăng dần. Giờ đây bài toán đã dễ dàng hơn trước rất nhiều.
>:::

### Subtask 1 + 2:

==Quy hoạch động cái túi (knapsack) cơ bản.==

Định nghĩa $f_{i,j}$ là số cách tạo thành tổng $j$ khi xét $i$ phần tử đầu tiên trong mảng.

Khi đó, ta xét cho từng $l_i$ là độ dài lớn nhất trong đa giác, $sum$ là tổng lớn nhất có thể tạo được với $l_j \le l_i$ đáp án tương ứng sẽ là:
$$
\sum_{j = l_i + 1}^{sum} f_{i-1, j}
$$

Lấy tổng đáp án tương ứng với từng giá trị $l_i$, ta sẽ có kết quả của bài.

Độ phức tạp thời gian: $O \left( n^3 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6, MOD = 1e9+7;
int n, a[N+5];
long long res, f[N+5];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    sort(a + 1, a + 1 + n);

    int sum = 0;

    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
        if (i >= 3) {
            for (int j = a[i] + 1; j <= sum; j++) {
                (res += f[j]) %= MOD;
            }
        }

        for (int j = sum; j >= a[i]; j--) {
            (f[j] += f[j - a[i]]) %= MOD;
        }
    }

    cout << res;
}

int main() {
    solve();
    return 0;
}

:::

### Subtask 3:
Thay vì đếm số cách chọn, ta có thể đếm phần bù, tức là đếm số lượng cách chọn không thể tạo thành đa giác lồi. Tức là $l_{i_1}+l_{i_2}+\dots+l_{i_{k-1}} \le l_{i_k}$.

Sau đó sử dụng loại trừ các đáp án không hợp lệ để có đáp án bài toán.

:::success
:::spoiler Code

#include<bits/stdc++.h>
using namespace std;

const int N = 5005, MOD = 1e9+7;

int n, a[N];
long long dp[N][N];

long long Pow(long long a, int k) {
    long long res = 1;
    while (k > 0) {
        if (k % 2 == 1) {
            (res *= a) %= MOD;
        }
        (a *= a) %= MOD;
        k /= 2;
    }    
    return res;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    sort(a+1,a+1+n);
    
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 5000; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= a[i]) {
                (dp[i][j] += dp[i-1][j-a[i]]) %= MOD;
            }
        }
    }
    
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= a[i]; j++) {
            res += dp[i-1][j];
            res %= MOD;
        }
    }
    
    cout << ((Pow(2,n)-1-res) % MOD + MOD) % MOD;
    
    return 0;
}

:::