## solution

DP on intervals. $O(N^3)$.

let $\operatorname{dp}_{[l,r)} = (\text{the minimal cost to make } [l,r) \text{ satisfy the condition})$. Compute this. The interval satisfying the condition is generated by some rules:

• A cycle makes such an interval.
• $\operatorname{dp}_{[l,r)} \gets w_{1,l} + w_{2,l} + w_{2,l+1} + \dots + w_{2,r-2} + w_{1,r-2}$.
• An interval can be extended by simply adding a vertex.
• $\operatorname{dp}_{[l,r)} \gets \operatorname{dp}_{[l,r-1)} + w_{1,r-2} + w_{2,r-3}$ (the left side).
• Two such intervals can be merged.
• $\operatorname{dp}_{[l,r)} \gets \operatorname{dp}_{[l,m+1)} + \operatorname{dp}_{[m,r)}$ for some $m$.

The DP table can be reduced to a $1$-ary one, by fixing as $l = 0$. This makes the complexity $O(N^2)$.

## implementation

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
class BiconnectedDiv1 { public: int minimize(vector<int> w1, vector<int> w2); };

const int inf = 1e9+7;
int BiconnectedDiv1::minimize(vector<int> w1, vector<int> w2) {
int n = w1.size() + 1;
vector<int> w2acc(n-1); repeat (i,n-2) w2acc[i+1] = w2acc[i] + w2[i];
vector<vector<int> > dp(n, vector<int>(n+1, inf)); // [l, r)
repeat_from (len,3,n+1) repeat (l,n) {
int r = l + len;
if (n < r) break;
dp[l][r] = w1[l] + w2acc[r-2] - w2acc[l] + w1[r-2];
setmin(dp[l][r], w1[l] + w2[l] + dp[l+1][r]);
setmin(dp[l][r], dp[l][r-1] + w1[r-2] + w2[r-3]);
repeat_from (m,l,r) setmin(dp[l][r], dp[l][m+1] + dp[m][r]);
}
return dp[0][n];
}