**Chủ đề là DP trên cây nên các bạn đừng làm tham nhé 😑**

Các bài quy ước $1$ là gốc cây.

## Bài 1: [Tô màu cây](https://marisaoj.com/problem/230)
- Trạng thái DP: $f(u, i)$ là số lượng đỉnh đen lớn nhất khi tô hết cây con gốc $u$ và $u$ có màu $i$. Quy ước $0$ là màu trắng còn $1$ là màu đen.
- Cập nhật:
+ $f(u,0)=\sum{max(f(v,1), f(v,0))}$ với $v$ là con trực tiếp của $u$. Do $u$ màu trắng nên các con $v$ có thể màu trắng hoặc đen.
+ $f(u,1)=\sum{f(v,0)}$, do $u$ đen nên các con $v$ chỉ có thể là màu trắng.

- Đáp án là $max(f(1,0/1))$.

Code
:::spoiler

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

const int MAXN = 1e5;

vector<int> adj[MAXN+5];
int dp[MAXN+5][2];

void dfs(int u, int p) {
    dp[u][0] = 0;
    dp[u][1] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][1]) << endl;
    return 0;
}

:::

## Bài 2: [Tô màu cây 2](https://marisaoj.com/problem/232)
- Trạng thái DP: $f(u,i)$ là số lượng cách tô màu khi tô hết cây con gốc $u$ và $u$ có màu $i$. $i$ từ $0$ tói $2$
- Cập nhật:
+ $f(u,0)=\prod{(f(v,1) + f(v,2))}$, do với mỗi đỉnh $v$, ta có thể tô hoặc là màu $1$ hoặc là màu $2$.
+ Tương tự với các màu còn lại.
- Đáp án $f(1,1)+f(1,2)+f(1,3)$.

Code:
:::spoiler

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

#define int long long

const int MOD = 1e9 + 7;
const int MAXN = 1e5;

vector<int> adj[MAXN + 1];
int dp[MAXN + 1][3];

void dfs(int u, int p) {
    dp[u][0] = dp[u][1] = dp[u][2] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        dp[u][0] = (dp[u][0] * (dp[v][1] + dp[v][2])) % MOD;
        dp[u][1] = (dp[u][1] * (dp[v][0] + dp[v][2])) % MOD;
        dp[u][2] = (dp[u][2] * (dp[v][0] + dp[v][1])) % MOD;
    }
}

signed main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    int ans = (dp[1][0] + dp[1][1] + dp[1][2]) % MOD;
    cout << ans << endl;
    return 0;
}

:::

## Bài 3: [Đường đi có tổng lớn nhất](https://marisaoj.com/problem/229)
- Trước tiên, đương đi đơn có 2 dạng như sau, một số bạn chỉ tính dạng 1 thì sai:

- Nhưng trước tiên, cứ tính dạng 1 trước với trạng thái $f(u)$ là giá trị đường đi có tổng lớn nhất bắt đầu ở $u$.
- Cập nhật:
+ $f(u)=max(0,max(f(v))+a_u$. Có thể nối $u$ với một đường đi bắt đầu ở $v$ nào đó, hoặc không bắt đầu một đường đi mới chỉ có mỗi $u$.
- Để xử lí trường hợp đường đi thứ 2, với mọi $u$, chọn ra $v$ và $v'$ là con trực tiếp của $u$ sao cho $f(v)$ và $f(v')$ lớn nhất, nối đường đi từ $v$ lên $u$ xuống $v'$.
- Đáp án là $max(f(u))$.

Code
:::spoiler

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

const int MAXN = 1e5;
#define int long long

vector<int> adj[MAXN+5];
int A[MAXN+5];
int dp[MAXN+5];
int ans = LLONG_MIN;

void dfs(int u, int p) {
    dp[u] = A[u];
    vector<int> f;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        dp[u] = max(dp[u], A[u] + dp[v]);
        f.push_back(dp[v]);
    }

    sort(f.begin(), f.end(), greater<int>());
    if(f.size() > 1) ans = max(ans, A[u] + f[0]+ f[1]);
}


signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

:::

## Bài 4: [Đường đi độ dài k](https://marisaoj.com/problem/231)
- Tương tự bài trên, trạng thái DP để tính đường đi loại 1: $f(u,i)$, số lượng đường đi bắt đầu ở $u$ và có độ dài $i$.
- Cập nhật:
+ $f(u,i)=\sum{f(v,i-1)}$.
- Với đường đi loại 2, ví dụ ta nối một đường đi từ $v$ lên $u$, từ $u$ sẽ phải xuống một đỉnh $v'$ khác. Nếu nối một đường đi độ dài $p$ từ $v$ lên $u$, thì $v'$ phải có độ dài $k - p - 1$. Nghĩa là tính tổng:
$f(v,p) \times f(v',k-p-1)$ với $v'$ khác $v$.

Code
:::spoiler

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

#define int long long

const int MAXN = 1e5;
const int MAXK = 100;

vector<int> adj[MAXN+5];
int dp[MAXN+5][MAXK+5];
int n, k;
int ans = 0;

void dfs(int u, int p) {
    dp[u][0] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        for (int i = 1; i <= k; i++) {
            dp[u][i] += dp[v][i-1];
        }
    }

    // for(int i = 1; i <= k; i++) cout << dp[u][i] << ' ';
    // cout << endl;
    
    int t = 0;
    for (int v : adj[u]) {
        if(v == p) continue;
        for(int i = 1; i < k; i++){
            t += dp[v][i - 1] * (dp[u][k - i] - dp[v][k - i - 1]);
        }
    }
    ans += t / 2;
    //cout << ans << endl;
}

signed main() {
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(3, 0);
   // cout << ans << endl;
    for (int i = 1; i <= n; i++) {
        ans += dp[i][k];
    }
    cout << ans << endl;
    return 0;
}

:::