# Quy hoạch động trên cây (DP on tree)
### Kiến thức cần biết
* [DFS (Depth first search)](https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/)
* [BFS (Breadth first search)](https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/)
* [Quy hoạch động (Dynamic Programming)](https://www.geeksforgeeks.org/dynamic-programming/)
## 1. Lý thuyết về cây
Cây là đồ thị vô hướng đặc biệt có tính chất sau:
* Là đồ thị liên thông và không có chu trình.
* Luôn có 1 đường đi giữa 2 đỉnh bất kì.
* Khi bỏ đi 1 cạnh bất kì thì cây phân thành 2 cây con.


Các bài toán về quy hoạch động trên cây thường sử dụng phép duyệt DFS (Depth First Search).

## 2. Phương pháp quy hoạch động
**Bước 1:** Tìm kết quả của bài toán con nhỏ nhất *(Trường hợp cơ sở)*.

**Bước 2:** Suy ra công thức truy hồi.

**Bước 3:** Tạo một bảng lưu kết quả của các bài toán con sau đó tính theo công thức đã suy ra.

**Bước 4:** Thông qua các bài toán con đã giải để tìm ra kết quả của bài toán.

## 3. Quy hoạch động trên cây
Phương pháp quy hoạch động trên cây chủ yếu dựa vào các tính chất đặc biệt của cây. Vậy nên trong các bài tập, ta cần xác định quan hệ cha - con. Các bài tập thường cần đến thao tác cập nhật dữ liệu từ các nút con lên $u$, và cập nhật các nút cha xuống dưới $u$.

Việc xác định quan hệ cha - con trong cây thì ta có thể sử dụng phép duyệt DFS, khi đó những đỉnh $v$ được thăm tiếp theo trong quá trình duyệt đỉnh $u$ sẽ nhận đỉnh $u$ là cha (nghĩa là khi duyệt từ đỉnh $u$ đến đỉnh $v$ thì cha của đỉnh $v$ là đỉnh $u$).

Thuật toán DFS được cài đặt linh hoạt tùy vào bài toán cụ thể.

## 4. Bài tập ứng dụng
**Bài toán 1:** Có $n$ vị trí, trong đó vị trí 1 là nguồn nước, còn $n - 1$ vị trí còn lại là nơi tiêu thụ nước. Mỗi nơi tiêu thụ nước có 1 ống dẫn nước từ nơi tiêu thụ nước khác hoặc nguồn nước. Biết rằng có 1 giây để nước chảy hết từ vị trí này qua vị trí khác bằng 1 ống dẫn nước. Hỏi sau khi nguồn nước bắt đầu chảy thì bao lâu sau vị trí $i$ nhận được nước ?

**Input:** Dòng đầu tiên nhập $n$ sau đó $n - 1$ dòng tiếp theo mỗi dòng nhập hai số $u$ và $v$ biểu thị một cạnh của đồ thị.

**Output:** Gồm $n - 1$ dòng là khoảng cách từ đỉnh 1 tới các đỉnh khác (từ $2$ đến $n$).

**Sample input:**

4
1 3
2 1
3 4

**Sample output:**

1
1
2

**Nhận xét:**
* Vì nước mất 1 giây để chảy từ vị trí này qua vị trí khác nên ta dễ dàng suy ra được công thức: $dp[v] = dp[u] + 1$.
* Ta duyệt DFS đến các đỉnh kề với đỉnh $u$ ngoại trừ cha của nó.

**Code:**

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

#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define eb emplace_back
#define ll long long

#define maxn 100005 
int n, dp[maxn];
vector<int> a[maxn];     
void dfs(int u, int p) { // p là cha của u
    for (int v : a[u]) {
        if(p != v) { // Duyệt tất cả đỉnh kề với u ngoại trừ nút cha của nó ra
            dp[v] = dp[u] + 1; // Đi từ v sang u (nghĩa là chi phí tới v sẽ là thg trc đó + thêm 1)
            dfs(v, u);
        }
    }
}
void decipher() {
    cin >> n;
    for (int i = 1; i < n; i++) {
    	int x, y; cin >> x >> y;
    	a[x].eb(y);
    	a[y].eb(x);
    }
    dfs(1, -1); // Ta cho mặc định cha của nút đầu tiên = -1
    for (int i = 2; i <= n; i++) cout << dp[i] << " ";
}

int main() {
    fastIO
    decipher();
    cerr << "Times: " << TIME << "s." << '\n';
    return 0;
}

\
**Bài toán 2:** Cho 1 cây có $n$ đỉnh và $n - 1$ cạnh có nút gốc là $c$. Tìm số nút con của mỗi nút (bao gồm cả chính nó).
**Sample input:**

4 2
1 3
2 1
3 4

**Sample output:**

3 4 2 1

**Nhận xét:**
* Ta duyệt DFS như thông thường, khi duyệt tới đỉnh cuối cùng ta sẽ +1 vào mảng lưu kết quả (số nút con của nó là chính nó). Suy ra $dp[u]$++.
* Sau đó cứ mỗi lần backtrack ta cộng số lượng nút con từ cuối về. Suy ra $dp[u] = dp[u] + dp[v]$.
+ Đỉnh 2 có 4 nút con (2, 1, 3, 4).
+ Đỉnh 1 có 3 nút con (1, 3, 4).
+ Đỉnh 3 có 2 nút con (3, 4).
+ Đỉnh 4 có 1 nút con (4).

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

#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define eb emplace_back
#define ll long long
#define maxn 100005

int n, c, dp[maxn];
vector<int> a[maxn];
void dfs(int u, int p) {
    for (int v : a[u]) {
        if (v != p) {
            dfs(v, u);
            dp[u] += dp[v];		
        }
    }
    dp[u]++;
}                        
void decipher() {
    cin >> n >> c;
    for (int i = 1; i < n; i++) {
    	int x, y; cin >> x >> y;
    	a[x].eb(y);
    	a[y].eb(x);
    }
    dfs(c, -1);
    for (int i = 1; i <= n; i++) cout << dp[i] << " ";
}

int main() {
    fastIO
    decipher();
    cerr << "Times: " << TIME << "s." << '\n';
    return 0;
}