Asia EC Online 2025 (I)——D. Min-Max Tree（树上dp）

思路讲解

参考代码

https://qoj.ac/submission/1298127

okay，我们来看一下，其实还是比较难的，没那么简单。

一开始我们想的是一个贪心，但是没那么贪，毕竟过的人比较少，说明大概率就是dp。

或者说容易想到，将一张图分为若干单调链一定是对的，但是怎么分那？这个就需要树上dp。

首先我们发现这个树上dp需要的是整体的值，但是我们计算的时候又需要的是单块的值，这个整体与局部的矛盾怎么解决那？那么dp计算肯定是我们优先考虑的，于是我们将局部的也并入dp。

// dp[i][0] 表示闭合收益 dp[i][1]表示上交最小链收益 
// dp[i][2] 表示上交最大链收益
arr3 dp[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];
}

AC代码

https://qoj.ac/submission/1303005

源代码

// 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……）