Subtask 1:

In this subtask no edges initially exist in the graph, so we will be adding all edges, which will then form a tree. In the dfs tree, the set of nodes in any subtree must form a contiguous range, so we can use range dp. Define $dp(i, j)$ to be the minimum cost on the range $[i, j]$, where $i$ is the root of a subtree connected to some series of subtrees under it containing the nodes $[i+1, j]$. Then

This represents adding the subtree $[k+1, j]$ onto the existing subtree rooted at $i$ connected by the edge $i\to k+1$. The overall time complexity is $O(N^3)$.

My code:

#include <bits/stdc++.h>
using namespace std;
 
const int mxN=750, INF=1e9;
int n, a[mxN][mxN], dp[mxN][mxN];
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; ++i)
		for (int j = 0; j < i; ++j)
			cin >> a[j][i], a[i][j] = a[j][i];
	for (int i = n - 1; i >= 0; --i)
		for (int j = i + 1; j < n; ++j) {
			dp[i][j] = INF;
			for (int k = i; k < j; ++k)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + a[i][k + 1]);
		}
	cout << dp[0][n - 1];
	return 0;
}

Subtask 2:

This is similar to the previous subtask, except now we have to consider removal of edges. The new range $[k+1, j]$ should have no edges to any node in $[i+1, k]$ (otherwise the cross-linking between subtrees will violate the dfs ordering). Define

or the cost to remove all edges between $[i, k]$ and $[k+1, j]$. Our updated dp is then The overall time complexity is $O(N^5)$.

#include <bits/stdc++.h>
using namespace std;
 
const int mxN=750, INF=1e9;
int n, a[mxN][mxN], dp[mxN][mxN];
 
// note this is defined slightly differently
int cut(int l, int m, int r) {
	int res = 0;
	for (int i = l; i < m; ++i)
		for (int j = m; j <= r; ++j)
			res += max(-a[i][j], 0);
	return res;
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; ++i)
		for (int j = 0; j < i; ++j)
			cin >> a[j][i], a[i][j] = a[j][i];
	for (int i = n - 1; i >= 0; --i)
		for (int j = i + 1; j < n; ++j) {
			dp[i][j] = INF;
			for (int k = i; k < j; ++k)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + max(0, a[i][k + 1]) + cut(i + 1, k + 1, j));
		}
	cout << dp[0][n - 1];
	return 0;
}

Full Solution:

The full solution follows from computing $cut$ faster. This can be done with precomputation and prefix sums. Define 2d prefix sum Then we can rewrite This runs in $O(N^3)$.

#include <bits/stdc++.h>
using namespace std;
 
const int mxN=750, INF=1e9;
int n, a[mxN][mxN], dp[mxN][mxN], p[mxN][mxN];
 
int cut(int l, int m, int r) {
	if (l >= m || m > r)
		return 0;
	return p[l][r] - p[l][m - 1] - p[m][r];
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; ++i)
		for (int j = 0; j < i; ++j)
			cin >> a[j][i], a[i][j] = a[j][i];
	for (int i = n - 1; i >= 0; --i)
		for (int j = i + 1; j < n; ++j) {
			p[i][j] = p[i + 1][j] + p[i][j - 1] - p[i + 1][j - 1] + max(-a[i][j], 0);
			dp[i][j] = INF;
			for (int k = i; k < j; ++k)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + max(0, a[i][k + 1]) + cut(i + 1, k + 1, j));
		}
	cout << dp[0][n - 1];
	return 0;
}