Islands [bug]

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> II;

const int N(1000001);
const int WHITE(0);
const int GREY(1);
const int BLACK(2);
const ll INF(1e9);

vector<pair<int,int> > V[N], cycle[N];
ll lengthpath[N];
int numcomponent;
bitset<N> incycle;
bitset<N> visited;
char color[N];
int parent[N];
int component[N];

bool find_cycle(int node){
    bool foundcycle = false;
    int markcycle = -1, now = -1;
    stack<int> S;
    S.push(node);
    while(not S.empty()){
        int top = S.top();
        S.pop();
        if(visited[top]) continue;
        visited[top] = true;
        component[node] = numcomponent;
        for(int i = 0; i < (int)V[top].size(); ++i) S.push(V[top][i].first);
    }

    S.push(node);
    while(not S.empty()){
        int top = S.top();
        S.pop();
        if(color[top] == BLACK) continue;
        if(color[top] == GREY){
            color[top] = BLACK;
            continue;
        }
        color[top] = GREY;
        S.push(top);
        for(int i = 0; i < (int)V[top].size(); ++i){
            if(V[top][i].first == parent[top]) continue;
            if(color[V[top][i].first] == GREY){
                foundcycle = true;
                markcycle = V[top][i].first;
                now = top;
                cycle[numcomponent].push_back(V[top][i]);
                break;
            }
            S.push(V[top][i].first);
            parent[V[top][i].first] = top;
            lengthpath[V[top][i].first] = V[top][i].second;
        }
        if(foundcycle) break;
    }
    if(not foundcycle) return false;
    while(now != markcycle){
        incycle[now] = true;
        cycle[numcomponent].push_back(make_pair(now, lengthpath[now]));
        now = parent[now];
    }
    incycle[markcycle] = true;
    return true;
}

bool firsttime;
ll subopt;
ll opt[N];

ll calcdyn(int node){
    if(firsttime) firsttime = false;
    else if(incycle[node]) return -INF;
    if(visited[node]) return opt[node];
    visited[node] = true;
    ll vmax = 0, vmax2 = 0;
    for(int i = 0; i < (int)V[node].size(); ++i){
        if(parent[node] == V[node][i].first) continue;
        parent[V[node][i].first] = node;
        ll val = calcdyn(V[node][i].first) + (ll)V[node][i].second;
        if(val > vmax){
            vmax2 = vmax;
            vmax = val;
        }else if(val > vmax2){
            vmax2 = val;
        }
        subopt = max(subopt, vmax + vmax2);
    }
    return opt[node] = vmax;
}

ll dynamic_tree(int node){
    firsttime = true;
    subopt = 0;
    return calcdyn(node);
}

II sum[N], cul[N];
int p[N];

ll solve(vector<ll>& node, vector<ll>& edge){
    sum[0] = cul[0] = II(node[0], 0);
    for(int i = 1; i < (int)node.size(); ++i)
        sum[i] = cul[i] = II(cul[i - 1].first - node[i - 1] + edge[i - 1] + node[i], i);

    sort(sum, sum + node.size(), greater<II>());
    ll ans1 = 0;
    int pointer = 0;
    for(int i = 0; i < (int)node.size() - 1; ++i){
        if(sum[pointer].second <= i) pointer++;
        ans1 = max(ans1, (node[i] << 1) + sum[pointer].first - cul[i].first);
    }
    ll ans2 = 0;
    ll cultivate = node.back();
    pointer = 0;
    for(int i = (int)node.size() - 2; i >= 0; --i){
        while(sum[pointer].second > i) pointer++;
        ans2 = max(ans2, cultivate + sum[pointer].first);
        cultivate += edge[i] + node[i] - node[i + 1];
    }
    return max(ans1, ans2 + edge.back());
}

int main(){
    int n, a, b;
    ll ans = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d %d", &a, &b);
        if(i == a) continue;
        if(a < i and p[a] == i){
            for(int j = 0; j < (int)V[i].size(); ++j)
                if(V[i][j].first == a) V[i][j].second = max(V[i][j].second, b);
            for(int j = 0; j < (int)V[a].size(); ++j)
                if(V[a][j].first == i) V[a][j].second = max(V[a][j].second, b);
            continue;
        }
        p[i] = a;
        V[i].push_back(make_pair(a, b));
        V[a].push_back(make_pair(i, b));
    }
    for(int i = 1; i <= n; ++i){
        if(V[i].size() == 0) continue;
        if(visited[i]) continue;
        if(not find_cycle(i)) cycle[numcomponent].push_back(II(i, -1));
        numcomponent++;
    }
    for(int i = 0; i < N; ++i) color[i] = WHITE, visited[i] = false, parent[i] = 0;
    for(int i = 0; i < numcomponent; ++i){
        if(not incycle[cycle[i][0].first]){
            ll tmp = dynamic_tree(cycle[i][0].first);
            ans += max(tmp, subopt);
            continue;
        }
        vector<ll> node, edge;
        node.push_back(dynamic_tree(cycle[i][0].first));
        ll anssub = subopt;
        for(int j = 0; j < (int)cycle[i].size() - 1; ++j){
            edge.push_back(cycle[i][j].second);
            node.push_back(dynamic_tree(cycle[i][j + 1].first));
            anssub = max(anssub, subopt);
        }
        edge.push_back(cycle[i].back().second);
        ans += max(anssub, solve(node, edge));
    }
    printf("%lld\n", ans);
    return 0;
}