# Phân Luồng Giao Thông

## Nguồn gốc và lý do lựa chọn

Đây là Bài 3 Contest *Trại hè Miền Trung – Tây Nguyên 2025*. Lý do mình chọn bài toán này là vì nó thuộc dạng Tree mà không đòi hỏi sử dụng các cấu trúc dữ liệu nâng cao như HLD hay Centroid Decomposition, đồng thời thuật toán chuẩn có xu hướng thiên về dạng tư duy logic hơn là cài đặt phức tạp, thứ mình nghĩ sẽ là những yếu tố để tạo nên một bài toán hay.

---
## Đề bài

Cho một cây có $N$ đỉnh và $N - 1$ cạnh. Giả sử $N - 1$ cạnh của cây là **có hướng**, cạnh thứ $i$ là $(x_i, y_i)$, biểu diễn hướng $x_i \to y_i$. Bạn có thể **đảo chiều** bất kỳ cạnh nào, sau đó chọn **ngẫu nhiên** hai đỉnh trọng điểm $A$ và $B$ *(có thể trùng)* sao cho sau khi đảo chiều các cạnh, từ mọi đỉnh trong cây tồn tại đường đi tới ít nhất một trong hai đỉnh $A$ hoặc $B$. **Yêu cầu:** tìm số lượng cạnh tối thiểu cần đảo chiều để tồn tại hai đỉnh $A$ và $B$ thỏa mãn điều kiện trên.

---
## Đầu vào

- Dòng đầu tiên gồm số nguyên $T$, thể hiện số lượng bộ test. Tiếp theo, dữ liệu trong mỗi bộ test được mô tả theo khuôn mẫu như sau:
+ Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 3000$).
+ Tiếp theo $N-1$ dòng, mỗi dòng chứa hai số nguyên $x_i\; y_i$, thể hiện cạnh có hướng $x_i \to y_i$.

- Dữ liệu đảm bảo tổng $N$ trên tất cả các bộ dữ liệu không vượt quá $9000$.

---

## Đầu ra

Với mỗi bộ dữ liệu, in ra một dòng duy nhất là một số nguyên $X$ là đáp án của bộ test tương ứng.

---
## Sample Input

2
10
3 1
3 4
5 4
5 2
7 2
8 2
6 1
6 9
10 6
3
2 1
3 1

## Sample Output

2
0

---
## Lời giải

### Nhận xét

Từ dữ liệu đề bài, ta thấy: $1 \leq N \leq 3000$, do đó ta sẽ tập trung tìm các giải thuật có độ phức tạp $\mathcal{O}(N^2)$ hoặc tương đương.

---

### Một số định nghĩa trong lời giải

- Gọi $F_u$ là số cạnh cần đảo chiều trong $\text{subtree}(u)$ để mọi đỉnh trong cây con này có thể đi đến $u$.
- Gọi $dp_u$ là số cạnh cần đảo chiều ít nhất để mọi đỉnh trong $\text{subtree}(u)$ có thể đi đến một đỉnh $A$ bất kỳ trong cây con này.
- Gọi $w(u, v)$ là trọng số của cạnh $u \to v$.

---

### Ý tưởng chính

- Đầu tiên, ta sẽ xử lý dữ liệu đầu vào một chút. Với mọi cạnh $x_i \to y_i$, ta sẽ biến đổi thành hai cạnh có dạng $(u, v, w)$ lần lượt là: $(x_i, y_i, 1)$ và $(y_i, x_i, 0)$

- Tiếp theo, ta sẽ thử từng đỉnh để làm gốc của cây, gọi đỉnh gốc hiện tại là $\text{curRoot}$. Đáp án sẽ nằm ở một trong hai trường hợp sau:

+ **Trường hợp 1:** Đỉnh $A$ và $B$ đều là $\text{curRoot}$.
$$ \text{Answer} = F_{\text{curRoot}}$$

+ **Trường hợp 2:** Đỉnh $A = \text{curRoot}$, còn $B \ne \text{curRoot}$
$$ \text{Answer} = \min_{u \ne \text{curRoot}} \left(F_{\text{curRoot}} - F_u + dp_u\right)$$

- Cách tính hai mảng $F$ và $dp$:

+ Đầu tiên là mảng $F$, giá trị $F_u$ là tổng trọng số các cạnh trong $\text{subtree}(u)$, ta có công thức: $$ F_u = \sum_{v \in \text{child}(u)} \left(F_v + w(u, v)\right)
$$

+ Tiếp theo là mảng $dp$, để tính $dp_u$, ta chia làm hai trường hợp sau:

1. Đỉnh $A$ được chọn chính là $u$, ta có công thức: $$dp_u = F_u$$

2. Đỉnh $A$ là một đỉnh khác $\ne u$ trong $\text{subtree}(u)$, công thức sẽ là: $$dp_u = \min_{v \in \text{child}(u)} \left(F_u - F_v + dp_v + (-1)^{w(u, v)}\right)$$

---

---
## Code mẫu

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

const int MAXN = 3005;
const int INF = 1e15;

int n;
int f[MAXN];
int dp[MAXN];
vector<pair<int, int>> g[MAXN];
int res = INF;
int curRoot = 0;

void DP(int u, int p) {
    dp[u] = f[u];
    for (pair<int, int> &x : g[u]) {
        int v, w; tie(v, w) = x;
        if (v == p) continue;
        DP(v, u);
        int lost_v = f[u] - f[v] - w + (w == 0);
        dp[u] = min(dp[u], lost_v + dp[v]);
    }
    if (u != curRoot) {
        res = min(res, dp[u] + f[curRoot] - f[u]);
    } else res = min(res, f[u]);
}

void dfs(int u, int p) {
    f[u] = 0;
    for (pair<int, int> &x : g[u]) {
        int v, w; tie(v, w) = x;
        if (v == p) continue;
        dfs(v, u);
        f[u] += f[v] + w;
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) g[i].clear();
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        g[x].push_back(make_pair(y, 1));
        g[y].push_back(make_pair(x, 0));
    }
    for (int root = 1; root <= n; ++root) {
        curRoot = root;
        dfs(root, 0);
        DP(root, 0);
    }
    cout << res << "\n";
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}