# Bài 1 ngày 1 VOI 25
**Lời giải chỉ mang tính chất tham khảo**
## Tóm tắt đề bài

### Mô tả
Ở một quốc gia nọ có $N$ hòn đảo, được đánh số lần lượt từ 1 đến $N$ . Có $N-1$ cây cầu, mỗi cây cầu nối trực tiếp 2 hòn đảo, tạo thành một quần thể đảo mà giữa hai hòn đảo bất kỳ luôn tồn tại đường đi thông qua một cây cầu hoặc một dãy các cây cầu.

Tuấn là một người giao hàng của công ty VOI. Ban đầu Tuấn ở hòn đảo 1, được giao $K$ nhiệm vụ giao hàng theo thứ tự từ 1 đến $K$ , và Tuấn phải xử lý các nhiệm vụ theo đúng thứ tự đó. Với nhiệm vụ thứ $i$ $( 1 \leq i \leq K )$ , Tuấn cần thực hiện giao hàng từ hòn đảo $U_i$ đến hòn đảo $V_i$ theo đường đi ghé qua ít hòn đảo nhất.

Tuấn chỉ có thể thực hiện nhiệm vụ giao hàng thứ $i$ nếu vị trí của Tuấn đang ở $U_i$ . Sau khi hoàn thành giao hàng, vị trí của Tuấn sẽ là $V_i$ .
Lưu ý:
- Đối với mỗi nhiệm vụ, Tuấn có thể **thực hiện** hoặc **từ chối** giao hàng.
- Đối với mỗi hòn đảo, công ty đặt một **giá trị phần thưởng** khi Tuấn ghé thăm hòn đảo đó (mỗi lần ghé qua).

Với mỗi nhiệm vụ hoàn thành, phần thưởng mà Tuấn nhận được là **giá trị lớn nhất** trong số các giá trị của các hòn đảo nằm trên đường đi giao hàng, bao gồm cả hòn đảo xuất phát và hòn đảo kết thúc.

**Yêu cầu:** Tính **tổng giá trị phần thưởng lớn nhất** mà Tuấn có thể nhận được sau $K$ nhiệm vụ.

---

## Dữ liệu

Dữ liệu được nhập từ file `SHIP.INP`:
- Dòng đầu tiên chứa một số nguyên $N$ là số lượng hòn đảo $( 1 \leq N \leq 2 \times 10^5)$ .
- Dòng thứ hai chứa $N$, số nguyên $W_1, W_2, \dots, W_N$ là giá trị phần thưởng của hòn đảo $i$ $( 1 \leq W_i \leq 10^9)$ .
- $N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $A$ và $B$ , mô tả cây cầu nối trực tiếp giữa hòn đảo $A$ và hòn đảo $B$ .
- Dòng tiếp theo chứa một số nguyên $K$ là số lượng nhiệm vụ giao hàng $( 1 \leq K \leq 2 \times 10^5)$.
- $K$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $U_i$ và $V_i$ , mô tả nhiệm vụ giao hàng từ hòn đảo $U_i$ đến hòn đảo $V_i$ $(1 \leq U_i, V_i \leq n, U_i \neq V_i)$

---

## Kết quả

- Ghi ra file `SHIP.OUT` một số nguyên duy nhất là tổng giá trị phần thưởng lớn nhất mà Tuấn có thể nhận được sau $K$ nhiệm vụ.

---

### Input

7
1 5 5 7 3 16 1
1 4
1 2
2 3
4 5
5 6
5 7
7
1 3
3 2
1 4
4 2
2 5
5 7
5 6

### Output

37

**Giải thích:**
- Tuấn thực hiện các nhiệm vụ 3, 4, 5, 7 từ chối các nhiệm vụ còn lại
- Tổng giá trị phần thưởng Tuấn nhận được là 7 + 7 + 7 + 16 = 37

---

## Lời giải:
Đầu tiên ta chia nhỏ bài toán thành 2 phần:
- Tìm **giá trị lớn nhất** từ $U_i$ tới $V_i$
- Tìm **phương án tối ưu** để thực hiện $K$ nhiệm vụ đạt được tổng lớn nhất

**Với phần đầu tiên:** ta có thể dễ dàng tìm ra lời giải bằng cách sử dụng kĩ thuật LCA (Lowest common ancestor) để tìm giá trị lớn nhất trên đường đi ngắn nhất từ $U_i$ tới $V_i$

**Với phần thứ hai:** Để tìm ra giá trị tối ưu nhất chúng ta sẽ sử dụng dp (Dynamic programming) để tính được giá trị lớn nhất đạt được tại $V_i$, **vì bài toán bắt buộc ta phải làm theo thứ tự $k$ đã cho trước và Tuấn bắt buộc phải đi từ vị trí 1** nên ta có thể có được công thức truy hồi sau:
- Base Case:
+ $dp[1] = 0$
+ $dp[2.. n] = -1e18$ hoặc $LLONG$_$MIN$
- Từ đây ta suy ra được công thức truy hồi sau với mỗi $U_i$ tới $V_i$ theo thứ tự $(1 \leq i \leq k)$
+ Gọi $max$_$path(u,v)$ là giá trị lớn nhất trên đường đi từ $U_i$ tới $V_i$
+ $dp[v] = max(dp[v], dp[u] +$ $max$_$path(u,v)$

Lúc này ta có được đáp án của bài toán bằng cách lấy $max(dp_1,dp_2,..,dp_n)$

---

## Code Mẫu
:::spoiler **Code**

#include <bits/stdc++.h>
#define fi first
#define se second
#define pir pair<int,int>
#define ll long long
#define pb push_back
#define el "\n"
using namespace std;
const int ME = 1e6+1;
int n = 0,k = 0;
vector<pir> adj[ME];
int cnt[ME] = {};
ll a[ME] = {};
ll d[ME][22];
ll maxi[ME][22];
ll depth[ME] = {};
ll dp[ME] = {};
ll res = 0;
void dfs(int u){
    for(auto i: adj[u]){
        int v = i.fi; ll w = i.se;
        if (!depth[v]){
            d[v][0] = u;
            maxi[v][0] = w;
            depth[v] = depth[u] + 1;
            for(int i = 1;i <= 20;i++){
                d[v][i] = d[d[v][i-1]][i-1];
                maxi[v][i] = max(maxi[v][i-1],maxi[d[v][i-1]][i-1]);
            }
            dfs(v);
        }
    }
    return;
}

ll max_path(int u,int v){
    ll ans = 0;
    if (depth[u] < depth[v]) swap(u,v);
    int dist = depth[u] - depth[v];
    for(int i = 0;i <= 20;i++){
        if (dist >> i & 1){
            ans = max(ans,maxi[u][i]);
            u = d[u][i];
        }
    }
    if (u == v) return ans;
    for(int i = 20;i >= 0;i--){
        if (d[u][i] != d[v][i]){
            ans = max({ans,maxi[v][i],maxi[u][i]});
            u = d[u][i];
            v = d[v][i];
        }
    }
    ans = max({ans,maxi[v][0],maxi[u][0]});
    return ans;
}

int main()
{
    freopen("SHIP.INP","r",stdin);
    freopen("SHIP.OUT","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        dp[i] = LLONG_MIN;
    }
    dp[1] = 0;
    for(int i = 1;i <= n-1;i++){
        int u = 0,v = 0,w = 0; cin >> u >> v;
        w = max(a[u],a[v]);
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    depth[1] = 1;
    dfs(1);
    cin >> k;
    for(int i = 1;i <= k;i++){
        int u = 0,v = 0; cin >> u >> v;
        dp[v] = max(dp[v],dp[u] + max_path(u,v));
        res = max(res,dp[v]);
    }
    cout << res << el;
    return 0;
}