#include <bits/stdc++.h>
using namespace std;
const int kN = 1e6 + 7;
struct FastVector{
long long arr[kN], sz;
FastVector(int sz = 0){
this->sz = sz;
}
void resize(int sz = 0){
this->sz = sz;
}
void clear(){
sz = 0;
}
void push_back(int x){
arr[sz++] = x;
}
long long& operator[](int idx){
return arr[idx];
}
inline int size(){
return sz;
}
};
vector<pair<int, int> > adj[kN];
bool vis[kN];
int depth[kN];
pair<long long, long long> get_diameter_length(int u, int par){
pair<long long, long long> ans{0, 0};
for(auto [to, len]: adj[u]){
if(to == par)
continue;
auto d = get_diameter_length(to, u);
ans.first = max(ans.first, d.first);
ans.first = max(ans.first, d.second + len + ans.second);
ans.second = max(ans.second, d.second + len);
}
return ans;
}
bool get_path(FastVector &path, int u, int par, const pair<int, int> &back_edge){
if(u == back_edge.second){
path.push_back(u);
return true;
}
for(auto [to, len]: adj[u]){
if(to == par )
continue;
if(get_path(path, to, u, back_edge)){
path.push_back(u);
return true;
}
}
return false;
}
long long get_longest_path_length(int u, int par, const int prohibited[]){
long long ans = 0;
for(auto [to, len]: adj[u]){
if(to == par || to == prohibited[0] || to == prohibited[1])
continue;
ans = max(ans, get_longest_path_length(to, u, prohibited) + len);
}
return ans;
}
FastVector path, longest_path[2];
int prohibited[2];
long long get_max_path(const pair<int, int> &back_edge, const int len_back_edge){
long long ans = get_diameter_length(back_edge.first, -1).first;
path.clear();
get_path(path, back_edge.first, -1, back_edge);
for(int i = 0; i < path.size() / 2; ++i)
swap(path[i], path[(int)path.size() - i - 1]);
longest_path[0].clear();
longest_path[1].clear();
for(int i = 0; i < 2; ++i)
longest_path[i].resize(path.size());
for(int i = 0; i < path.size(); ++i){
if(i == 0)
prohibited[0] = -1;
else
prohibited[0] = path[i - 1];
if(i == path.size() - 1)
prohibited[1] = -1;
else
prohibited[1] = path[i + 1];
longest_path[0][i] = longest_path[1][i] = get_longest_path_length(path[i], -1, prohibited);
}
long long curr_len = 0;
for(int i = 0; i < path.size(); ++i){
longest_path[0][i] += curr_len;
if(i != (int)path.size() - 1){
for(auto [to, len]: adj[path[i]]){
if(to == path[i + 1]){
curr_len += len;
break;
}
}
}
}
curr_len = 0;
for(int i = (int)path.size() - 1; i >= 0; --i){
longest_path[1][i] += curr_len;
if(i != 0){
for(auto [to, len]: adj[path[i]]){
if(to == path[i - 1]){
curr_len += len;
break;
}
}
}
}
for(int i = 1; i < path.size(); ++i)
longest_path[0][i] = max(longest_path[0][i - 1], longest_path[0][i]);
for(int i = (int)path.size() - 2; i >= 0; --i)
longest_path[1][i] = max(longest_path[1][i + 1], longest_path[1][i]);
for(int i = 0; i < (int)path.size() - 1; ++i)
ans = max(ans, longest_path[0][i] + longest_path[1][i + 1] + len_back_edge);
return ans;
}
void build_tree(int u, int par, vector<pair<int, int>> &back_edges, vector<int> &len_back_edges){
vis[u] = true;
if(par == -1)
depth[u] = 0;
else
depth[u] = depth[par] + 1;
bool to_del = false;
int ud, tod, lend;
for(auto [to, len]: adj[u]){
if(to == par)
continue;
if(vis[to]){
if(depth[to] > depth[u]){
back_edges.push_back({to, u});
len_back_edges.push_back(len);
to_del = true;
ud = u;
tod = to;
lend = len;
}
continue;
}
build_tree(to, u, back_edges, len_back_edges);
}
if(to_del){
adj[ud].erase(find(adj[ud].begin(), adj[ud].end(), pair{tod, lend}));
adj[tod].erase(find(adj[tod].begin(), adj[tod].end(), pair{ud, lend}));
}
}
vector<pair<int, int>> back_edges;
vector<int> len_back_edges;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for(int u = 1; u <= n; ++u){
int v, len;
cin >> v >> len;
adj[u].push_back({v, len});
adj[v].push_back({u, len});
}
for(int i = 1; i <= n; ++i){
if(!vis[i]){
build_tree(i, -1, back_edges, len_back_edges);
}
}
for(int i = 1; i <= n; ++i)
vis[i] = false;
long long ans = 0;
for(int i = 0; i < back_edges.size(); ++i)
ans += get_max_path(back_edges[i], len_back_edges[i]);
cout << ans << "\n";
}
Compilation message
islands.cpp: In function 'std::pair<long long int, long long int> get_diameter_length(int, int)':
islands.cpp:41:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [to, len]: adj[u]){
^
islands.cpp: In function 'bool get_path(FastVector&, int, int, const std::pair<int, int>&)':
islands.cpp:60:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [to, len]: adj[u]){
^
islands.cpp:60:19: warning: unused variable 'len' [-Wunused-variable]
for(auto [to, len]: adj[u]){
^
islands.cpp: In function 'long long int get_longest_path_length(int, int, const int*)':
islands.cpp:74:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [to, len]: adj[u]){
^
islands.cpp: In function 'long long int get_max_path(const std::pair<int, int>&, int)':
islands.cpp:118:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [to, len]: adj[path[i]]){
^
islands.cpp:131:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [to, len]: adj[path[i]]){
^
islands.cpp: In function 'void build_tree(int, int, std::vector<std::pair<int, int> >&, std::vector<int>&)':
islands.cpp:160:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [to, len]: adj[u]){
^
islands.cpp:181:58: error: missing template arguments before '{' token
adj[ud].erase(find(adj[ud].begin(), adj[ud].end(), pair{tod, lend}));
^
islands.cpp:182:61: error: missing template arguments before '{' token
adj[tod].erase(find(adj[tod].begin(), adj[tod].end(), pair{ud, lend}));
^
islands.cpp: In function 'int main()':
islands.cpp:214:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < back_edges.size(); ++i)
~~^~~~~~~~~~~~~~~~~~~
