Asia EC Online 2025 (I)——D. Min-Max Tree（树上dp） · znzryb
## 思路讲解
参考代码
[https://qoj.ac/submission/1298127](https://qoj.ac/submission/1298127)
okay，我们来看一下，其实还是比较难的，没那么简单。
一开始我们想的是一个贪心，但是没那么贪，毕竟过的人比较少，说明大概率就是dp。
或者说容易想到，将一张图分为若干单调链一定是对的，但是怎么分那？这个就需要树上dp。
首先我们发现这个树上dp需要的是整体的值，但是我们计算的时候又需要的是单块的值，这个整体与局部的矛盾怎么解决那？那么dp计算肯定是我们优先考虑的，于是我们将局部的也并入dp。
```cpp
// dp[i][0] 表示闭合收益 dp[i][1]表示上交最小链收益
// dp[i][2] 表示上交最大链收益
arr3 dp[MAXN];
```
具体代码看我注释吧。
```cpp
// dp[i][0] 表示闭合收益 dp[i][1]表示上交最小链收益 dp[i][2] 表示上交最大链收益
arr3 dp[MAXN];
void dfs(int u, int fa) {
ll a = A[u];
// 0 - closed with single point
// 1 - chain with minimum
// 2 - chain with maximum
// 3 - closed with two merged link
array<ll, 4> e = {0, -a, a, -INF};
for (auto &v : g[u]) {
if (v == fa) continue;
dfs(v, u);
// 上交最大链 与 最小链端
e[3] = max({A[u] < A[v] ? e[1] + dp[v][2] : -INF,
// 最大链端 与 上交最小链
A[u] > A[v] ? e[2] + dp[v][1] : -INF,
e[3] + dp[v][0]
});
// e[2] 可以怎么样拼出来那？
// 是不是我可以将 u 这个点作为单个点
// 向其上交这个最大值，相当于这个点作为一个单链
// 那么 就是 e[2] + dp[v][0]
// 你如果要和下面的块融合，那么就是dp[v][2]
// 当然我们还要考虑一下就是和别的分支的融合，那么就是e[0]+dp[v][2]。
e[2] = max(e[2] + dp[v][0],
A[u]<A[v]?e[0] + dp[v][2]:-INF
);
e[1] = max(e[1] + dp[v][0]
, (A[u]>A[v]?e[0]+dp[v][1]:-INF)
);
e[0] += dp[v][0];
}
dp[u][0]=max(e[3],e[0]);
dp[u][1]=e[1];
dp[u][2]=e[2];
}
```
## AC代码
[https://qoj.ac/submission/1303005](https://qoj.ac/submission/1303005)
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef _DEBUG
template<typename T> void _print(T x) {
cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
cerr << "[ ";
for (T i : v) _print(i), cerr << " ";
cerr << "]";
}
template<typename T> void _print(set<T> s) {
cerr << "{ ";
for (T i : s) _print(i), cerr << " ";
cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
cerr << "{";
_print(p.first);
cerr << ", ";
_print(p.second);
cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
cerr << "{ ";
for (auto &p : m) _print(p), cerr << " ";
cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif
using ll = long long; using ull = unsigned long long;
using ld = double; using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>; using plb = pair<ll, bool>;
using pll = pair<ll, ll>; using vll = vector<ll>; using vb = vector<bool>;
using tll = tuple<ll, ll, ll>; using vii = vector<int>;
using vpll = vector<pll>; using vtll = vector<tll>;
using vdb = vector<ld>; using vc = vector<char>;
using arr3 = array<ll, 3> ; using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9+7; // 998244353;
static constexpr double eps = 1e-8; const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;
inline void __();
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cin>>lT;
// while(lT--)
__();
return 0;
}
/*
*/
vector<ll> g[MAXN];
ll A[MAXN];
// dp[i][0] 表示闭合收益 dp[i][1]表示上交最小链收益 dp[i][2] 表示上交最大链收益
arr3 dp[MAXN];
void dfs(int u, int fa) {
ll a = A[u];
// 0 - closed with single point
// 1 - chain with minimum
// 2 - chain with maximum
// 3 - closed with two merged link
array<ll, 4> e = {0, -a, a, -INF};
for (auto &v : g[u]) {
if (v == fa) continue;
dfs(v, u);
// 上交最大链 与 最小链端
e[3] = max({A[u] < A[v] ? e[1] + dp[v][2] : -INF,
// 最大链端 与 上交最小链
A[u] > A[v] ? e[2] + dp[v][1] : -INF,
e[3] + dp[v][0]
});
// e[2] 可以怎么样拼出来那？
// 是不是我可以将 u 这个点作为单个点
// 向其上交这个最大值，相当于这个点作为一个单链
// 那么 就是 e[2] + dp[v][0]
// 你如果要和下面的块融合，那么就是dp[v][2]
// 当然我们还要考虑一下就是和别的分支的融合，那么就是e[0]+dp[v][2]。
e[2] = max(e[2] + dp[v][0],
A[u]<A[v]?e[0] + dp[v][2]:-INF
);
e[1] = max(e[1] + dp[v][0]
, (A[u]>A[v]?e[0]+dp[v][1]:-INF)
);
e[0] += dp[v][0];
}
dp[u][0]=max(e[3],e[0]);
dp[u][1]=e[1];
dp[u][2]=e[2];
}
inline void __() {
cin >> N;
FOR(i, 1, N) {
cin >> A[i];
}
FOR(i, 1, N - 1) {
ll u, v;
cin >> u >> v;
g[u].PB(v);
g[v].PB(u);
}
dfs(1, 1);
cout<<dp[1][0]<<"\n";
}
/*
参考代码
https://qoj.ac/submission/1298127
AC
https://qoj.ac/submission/1303005
*/
```
:::
## 心路历程（WA，TLE，MLE……）