# A5 - DP trên DAG

## B1: Đường đi có tổng trọng số lớn nhất

### Vì sao không dùng Dijkstra được?
https://stackoverflow.com/questions/8027180/dijkstra-for-longest-path-in-a-dag

### Sol
Đặt $dp(u)$ là đường đi dài nhất tới $u$.
Để đi tới $u$, thì trước đó ta đã ở một đỉnh $v$ nào đó (mà có cung $v \rightarrow u$ trong input).
Công thức: $dp(u) = \max dp(v) + 1$
Vì gọi đệ quy, tính theo chiều ngược thay vì chiều thuận nên chỉ cần

for u := 1 to n do
    ans := max(ans, dp(u));

Và thêm mảng nhớ vào đệ quy.

### Bày code

const int N = 1e5 + 50;
int f[N]; //khởi tạo = -1 nghĩa là chưa tính
int dp(int u) {
    if (f[u] != -1) return f[u];
    for (auto v : cha[u])
        f[u] = max(f[u], dp(v) + 1);
    return f[u];
}

## B2: SCONNECT
Làm y hôm bữa

## B3: NEWROADS
### Đề bài
Cho đồ thị có hướng. $A,B$ là cặp thành phố thân thiện nếu như $A$ và $B$ đi tới được nhau qua các cung cho trước.
Cần nối thêm đường giữa những cặp thân thiện.

### Sol
Điều kiện $\Leftrightarrow A,B$ thuộc cùng TPLT mạnh. Vậy trước tiên có thể làm như B2.
Sau đó, giả sử phát hiện một TPLT mạnh có $v$ đỉnh và $e$ cung.
Số cung tổng cộng là $v(v-1)$. Vậy số cung cần thêm là $v(v-1) - e$

### Quick note
Ba bài sau sẽ nâng cao hơn phần nào

## B6:
Dễ hơn B4
### Tóm tắt
Máy $(a_i, b_i)$ coi như là một cung của đồ thị. Đề hỏi: Với mọi $a,b$ được xét đến (có cung $a \rightarrow b$ trong input) thì có thỏa mãn:
$a$ đi tới được $b$ **hoặc** $b$ đi tới được $a$

### Tiếp cận
#### TH không thỏa mãn
$1,3$ không thỏa mãn.
Tương tự như hình sau:

#### TH thỏa mãn
Tất cả các đỉnh phải "nằm trên một đường".
Nếu áp dụng B1, có nghĩa là đường đi dài nhất $=$ số lượng đỉnh cần quan tâm.
Chứng minh:

## B4: (VOI)
Đồ thị đã cho có dạng "nằm trên một đường" như bài 6.
Chỉ cần nối thêm một cung nữa để tạo thành một TPLT mạnh có kích thước bằng đúng $n$

## B5: (APIO)
Đường đi dài nhất nhưng đồ thị được cho chưa phải là DAG.
Vậy cần áp dụng B2 để nén thành các TPLT mạnh trước.
Trọng số là tổng thay vì $1$