题目链接

---

题目大意：

一棵树，加强第 $i$ 个点有 $w_i$ 的花费，而如果距离某
个点 $\le p$ 的所有点都加强了，则会有 $v_p$ 的收益，求最大净收益。

---

解题思路：

树形dp做法想不明白为啥是对的？？qwq
大佬的代码仅供参考，有看懂的聚聚留言qwq

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n;vector<int> a(n), b(n);for(int i = 0; i < n; ++i) cin >> a[i];for(int i = 0; i < n; ++i) cin >> b[i];vector<vector<int>> g(n);for(int i = 1; i < n; ++i) {int u, v;cin >> u >> v;--u, --v;g[u].push_back(v);g[v].push_back(u);}vector<vector<int>> dp(n, vector<int>(n + 1, -1e9));function<void(int,int)> dfs = [&](int u, int fa) {dp[u][0] = 0;for(int i = 1; i <= n; ++i) {dp[u][i] = b[i - 1] - a[u];}for(int v : g[u]) {if(v == fa) continue;dfs(v, u);vector<int> ndp(n + 1, -1e9);for(int q = 0; q <= n; ++q) {// dp[u][q]: 和 u 距离小于 q 的点都被选择了// 那么对于 v 来说，和 v 距离小于 q - 1 的点显然必须被选择for(int p = max(0, q - 1); p <= min(n, q + 1); ++p) {if(1) ndp[q] = max(ndp[q], dp[v][p] + dp[u][q]);else ndp[q] = max(ndp[q],dp[u][q]);}}dp[u] = ndp;}};dfs(0, -1);cout << *max_element(dp[0].begin(), dp[0].end()) << '\n';
}

---

最小割模型

首先我们先把所有的收益全部加上去。现在就是要花费最小？
我们看$n=200$非常小，可以往网络流方向想，因为要花费最小，那么可以转成最小割去求

• 左边的点 $v_{i,p}$ 表示距离第 $i$ 个点 $\le p$ 的所有点全选
• 右边的点 $ui$ 表示原图的点 $i$
• 源点连向每个 $v_{i,p}$，容量为增量收益 $v_{i,p}-v_{i,p-1}$，割掉这条边表示放弃这个增量收益
• 每个 $v_{i,p}$ 连向右边距离 $i$ 为 $p$ 的点，容量为无穷大
• 每个 $v_{i,p}$ 连向 $v_{i,p-1}$，容量为无穷大，这样使得 $v_{i,p}$ 间接连
• 向与 $i$ 距离 $<p$ 的点，用来限制放弃收益必须按 $p$ 从大到小放弃
• 右边每个点连向汇点，容量为选这个点的代价，割掉这条边
  表示付出这个点的代价
• 答案减去最小割。

---

AC code

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl '\n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 9;
const int maxn = 6e6 + 10;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {read(first);read(args...);
}int n, m, s, t;
struct node {int to, nxt, len;
}e[maxn];int head[maxn], cnt;inline void add(int from, int to, int len) {e[cnt] = {to,head[from],len};head[from] = cnt ++;e[cnt] = {from,head[to],0};head[to] = cnt ++;
}int d[maxn], cur[maxn];bool bfs() {ms(d,0);queue<int> q;q.push(s);d[s] = 1;while(!q.empty()) {int u = q.front();q.pop();for(int i = head[u]; ~i; i = e[i].nxt) {int v = e[i].to;if(d[v] || e[i].len <= 0) continue;q.push(v);d[v] = d[u] + 1; }}for(int i = 0; i <= t; ++ i) cur[i] = head[i];return d[t] != 0;
}int dfs(int u, int flow) {if(u == t) return flow;for(int &i = cur[u]; ~i; i = e[i].nxt) {int v = e[i].to;if(d[u] + 1 != d[v] || e[i].len <= 0) continue;int delta = dfs(v,min(flow,e[i].len));if(delta <= 0) continue;e[i].len -= delta;e[i^1].len += delta;return delta;}return 0;
}inline ll get_maxflow() {ll maxflow = 0, delta = 0;while(bfs()) {while(delta = dfs(s,INF)) {maxflow += delta;}}return maxflow;
}int w[202], v[202];
int G[202][202];
int poiidx[202];
int vipidx[202][202];
int idx;
int main() {IOS;ms(G,INF);ms(head,-1);cin >> n;for(int i = 1; i <= n; ++ i) cin >> w[i], G[i][i] = 0;for(int i = 0; i < n; ++ i) cin >> v[i];for(int i = 1; i < n; ++ i) {int u, v;cin >> u >> v;G[u][v] = G[v][u] = 1; }for(int k = 1; k <= n; ++ k)for(int i = 1; i <= n; ++ i)for(int j = 1; j <= n; ++ j)G[i][j] = min(G[i][k]+G[k][j],G[i][j]);s = 0;for(int i = 1; i <= n; ++ i) poiidx[i] = ++ idx;for(int i = 1; i <= n; ++ i) for(int p = 0; p < n; ++ p)vipidx[i][p] = ++ idx;t = ++ idx;for(int i = 1; i <= n; ++ i)for(int p = 0; p < n; ++ p) {add(s,vipidx[i][p],p?(v[p]-v[p-1]):(v[p]));if(p!=0) add(vipidx[i][p],vipidx[i][p-1],INF);} for(int i = 1; i <= n; ++ i) add(poiidx[i],t,w[i]);for(int i = 1; i <= n; ++ i) for(int j = 1; j <= n; ++ j) {int dist = G[i][j];add(vipidx[i][dist],poiidx[j],INF);}int ans = n*v[n-1];cout << ans - get_maxflow();return 0; 
}