## Nhận xét
Để tổng các giá trị trong đỉnh là lớn nhất thì tổng giá trị các đỉnh trong cây con đã xoá phải __nhỏ nhất__
Ta có một nhận xét quan trọng là:
> _Khi xoá một cây con $A$ thì ta không cần phải xoá cây con trong cây $A$ đó nữa_
Tức là những cây con bị xoá phải rời nhau (Hay $\nexists$ một cặp cây nào mà một cây là __cây con__ của cây còn lại)
Và khi ta __trải phẳng__ cây ra thành một [Euler Tour](https://wiki.vnoi.info/algo/graph-theory/euler-tour-on-tree.md) thì ta nhận ra những cây con là một đoạn trong mảng đó.
__Từ đó bài toán quy về thành__
> _Cho một mảng $a$, mỗi mảng có một nhãn và một giá trị (một nhãn chỉ xuất hiện **đúng hai lần**), hãy chọn không quá $k$ đoạn thoả mãn với mọi đoạn con thì __nhãn đầu tiên bằng nhãn cuối cùng__ sao cho tổng giá trị các đoạn phải là nhỏ nhất_
Ta nhận ra bài toán này có thể giải bằng phương pháp __quy hoạch động__
## Hướng giải
Gọi $dp[i][j]$ là giá trị nhỏ nhất khi chọn $k$ đoạn đoạn mà vị trí các đầu mút của __tất cả các đoạn__ đều bé hơn $i$
Ta có công thức như sau:
- Nếu nhãn ở vị trí thứ $i$ không xuất hiện ở một trong các vị trí $\in [1, i) \Rightarrow dp[i][j] = dp[i - 1][j]$
- Còn không thì ta có hai nghiệm ứng viên
- `uv1 = dp[i - 1][j]`
- `uv2 = dp[l_pre][j - 1] + getSum(lim[e[i]].l, lim[e[i]].r)`
- `getSum(i, j)` là tổng các giá trị trong đoạn từ $i$ đến $j$
- `lim[e[i]].l]` là vị trí nhãn `e[i]` ở bên trái
- `lim[e[i]].r]` là vị trí nhãn `e[i]` ở bên phải
- Và ta ghi nhận `dp[i][j] = min(dp[i][j], uv1, uv2)`
Cuối cùng, ta ghi nhận giá trị nhỏ nhất `minOut = min(dp[2 * n][i])` với $i \in [1, k]$
Cuối cùng, ta lấy tổng giá trị các đỉnh từ $1$ đến $n$ trừ đi `minOut` ta vừa tìm được là nghiệm của bài toán
__Độ phức tạp:__ $O(n \times k)$
## Code tham khảo
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int
maxN = 1e5,
maxK = 100,
oo = 1e18;
int n, k, cur;
vector <int> w[maxN + 1];
int vl_fst[maxN + 1],
a[2 * maxN + 1],
dp[2 * maxN + 1][maxK + 1],
p[2 * maxN + 1],
e[2 * maxN + 1];
struct Limit{
int l, r;
} lim[maxN + 1];
int getSum(int i, int j){
return p[j] - p[i - 1];
}
void init(){
cin>>n>>k;
for (int i = 1; i <= n; i++)
cin>>vl_fst[i];
for (int i = 1; i < n; i++){
int u, v; cin>>u>>v;
w[u].push_back(v);
w[v].push_back(u);
}
}
void dfs(int u, int pre){
lim[u].l = ++cur;
for (int v: w[u])
if (pre != v)
dfs(v, u);
lim[u].r = ++cur;
}
void make_ea(){
dfs(1, 0);
for (int i = 1; i <= n; i++){
e[lim[i].l] = i;
e[lim[i].r] = i;
a[lim[i].l] = vl_fst[i];
}
for (int i = 1; i <= 2 * n; i++)
p[i] = p[i - 1] + a[i];
}
void make_dp(){
for (int i = 1; i <= 2 * n; i++)
for (int j = 1; j <= k; j++)
dp[i][j] = oo;
for (int i = 1; i <= 2 * n; i++){
int val = e[i];
if (lim[val].l == i){
for (int j = 1; j <= k; j++)
dp[i][j] = dp[i - 1][j];
continue;
}
int l_pre = lim[e[i]].l - 1;
for (int j = 1; j <= k; j++){
int tmp,
uv1 = dp[i - 1][j],
uv2 = dp[l_pre][j - 1]
+ getSum(lim[e[i]].l, lim[e[i]].r);
if (dp[l_pre][j - 1] == oo)
tmp = uv1;
else tmp = min(uv1, uv2);
dp[i][j] = min(dp[i][j], tmp);
}
}
}
void solve(){
int org = getSum(1, 2 * n),
bu = 2e18;
for (int i = 1; i <= k; i++)
bu = min(bu, dp[2 * n][i]);
cout<<org - bu;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
init(); make_ea(); make_dp(); solve();
}
```
minhpnk2
Created at
0 likes