#include "shortcut.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<pair<int,int>> adj[N];
bool on_circle[N];
long long ret = 0;
long long dfs(int v,int par){
long long maxi = 0;
for(auto u:adj[v]){
if(u.first == par || on_circle[u.first])continue;
long long tmp = dfs(u.first,v) + u.second;
ret = max(ret,maxi + tmp);
maxi = max(maxi,tmp);
}
return maxi;
}
long long get_ans(vector<int> circle,vector<int> circle_edges){
// cout << "circle: ";
// for(auto u:circle){
// cout << u << " ";
// }
// cout << endl;
assert(circle.size() == circle_edges.size());
for(auto u:circle){
on_circle[u] = 1;
}
ret = 0;
vector<long long> depths;
for(auto u:circle){
depths.push_back(dfs(u,-1));
}
long long circle_length = 0;
for(auto u:circle_edges){
circle_length += u;
}
vector<long long> d = {0};
for(int i = 1;i<circle.size();i++){
d.push_back(d[i-1] + circle_edges[i-1]);
}
for(int i = 0;i<circle.size();i++){
for(int j = i+1;j<circle.size();j++){
ret = max(ret,min(d[j]-d[i],circle_length - (d[j] - d[i])) + depths[i] + depths[j]);
}
}
for(auto u:circle){
on_circle[u] = 0;
}
//cout << "ret: " << ret << endl;
return ret;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int nwedge)
{
for(int i = 0;i<n-1;i++){
adj[i].push_back({i+1,l[i]});
adj[i+1].push_back({i,l[i]});
}
for(int i = 0;i<n;i++){
adj[i].push_back({i+n,d[i]});
adj[i+n].push_back({i,d[i]});
}
long long ans = 1e18;
for(int i = 0;i<n;i++){
vector<int> circle;
vector<int> circle_edges;
for(int j = i;j<n;j++){
{
circle.clear();
circle_edges.clear();
for(int c = i;c<=j;c++){
circle.push_back(c);
if(c != i)
circle_edges.push_back(l[c-1]);
}
circle_edges.push_back(nwedge);
adj[i].push_back({j,nwedge});
adj[j].push_back({i,nwedge});
ans = min(ans,get_ans(circle,circle_edges));
adj[i].pop_back();
adj[j].pop_back();
}
/*
{
circle.clear();
circle_edges.clear();
for(int c = i;c<=j;c++){
circle.push_back(c);
if(c != i)
circle_edges.push_back(l[c-1]);
}
circle_edges.push_back(d[j]);
circle.push_back(j+n);
circle_edges.push_back(nwedge);
adj[i].push_back({j+n,nwedge});
adj[j+n].push_back({i,nwedge});
ans = min(ans,get_ans(circle,circle_edges));
adj[i].pop_back();
adj[j+n].pop_back();
}
{
circle.clear();
circle_edges.clear();
circle.push_back(i+n);
circle_edges.push_back(d[i]);
for(int c = i;c<=j;c++){
circle.push_back(c);
if(c != i)
circle_edges.push_back(l[c-1]);
}
circle_edges.push_back(nwedge);
adj[i+n].push_back({j,nwedge});
adj[j].push_back({i+n,nwedge});
ans = min(ans,get_ans(circle,circle_edges));
adj[i+n].pop_back();
adj[j].pop_back();
}
if(i != j){
circle.clear();
circle_edges.clear();
circle.push_back(i+n);
circle_edges.push_back(d[i]);
for(int c = i;c<=j;c++){
circle.push_back(c);
if(c != i)
circle_edges.push_back(l[c-1]);
}
circle_edges.push_back(d[j]);
circle.push_back(j+n);
circle_edges.push_back(nwedge);
adj[i+n].push_back({j+n,nwedge});
adj[j+n].push_back({i+n,nwedge});
ans = min(ans,get_ans(circle,circle_edges));
adj[i+n].pop_back();
adj[j+n].pop_back();
}*/
}
//cout << ans << endl;
}
return ans;
}
