เกาะกับสะพาน: เมื่อรูปของกราฟถูกล็อกไว้แล้ว เส้นทางยาวสุดเหลือแค่สองทรง

// เฉลยชุดทดสอบย่อย N ไม่เกิน 4,000 (40 คะแนน)
// ความคิดหลัก: ตัดเส้นบนวงออกทีละเส้น กลุ่มนั้นจะกลายเป็นต้นไม้ทันที
// แล้วเส้นทางยาวสุดในต้นไม้ก็คือเส้นผ่านศูนย์กลาง ซึ่งหาได้ด้วยการค้นสองรอบ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
struct E { int to, w, id; };
vector<vector<E>> g;                                // กราฟไม่มีทิศ สะพานสองเส้นระหว่างเกาะคู่เดียวกันเป็นคนละเส้น จึงต้องมีหมายเลขกำกับ

pair<int,ll> farthest(int s, const vector<char>& alive, int banId) {
    vector<ll> d(n + 1, -1);
    d[s] = 0;
    vector<int> st{s};
    int bi = s; ll bd = 0;
    while (!st.empty()) {
        int u = st.back(); st.pop_back();
        for (auto& e : g[u]) {
            int v = e.to;
            if (!alive[v] || d[v] >= 0 || e.id == banId) continue;   // ข้ามสะพานเส้นที่ตัดทิ้ง
            d[v] = d[u] + e.w;
            if (d[v] > bd) { bd = d[v]; bi = v; }
            st.push_back(v);
        }
    }
    return {bi, bd};
}

int main() {
    scanf("%d", &n);
    vector<int> f(n + 1), L(n + 1);
    g.assign(n + 1, {});
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &f[i], &L[i]);
        g[i].push_back({f[i], L[i], i});
        g[f[i]].push_back({i, L[i], i});
    }
    vector<char> seen(n + 1, 0);
    ll ans = 0;
    for (int s = 1; s <= n; s++) {
        if (seen[s]) continue;
        // เก็บสมาชิกของกลุ่มนี้
        vector<int> comp; vector<char> alive(n + 1, 0);
        vector<int> st{s}; seen[s] = 1;
        while (!st.empty()) {
            int u = st.back(); st.pop_back(); comp.push_back(u); alive[u] = 1;
            for (auto& e : g[u]) if (!seen[e.to]) { seen[e.to] = 1; st.push_back(e.to); }
        }
        // หาวงด้วยการเดินตามลูกศรจนวนกลับมาที่เดิม
        vector<int> mark(n + 1, 0);
        int u = s; while (!mark[u]) { mark[u] = 1; u = f[u]; }
        vector<int> cyc; int v = u;
        do { cyc.push_back(v); v = f[v]; } while (v != u);
        ll best = 0;
        for (size_t i = 0; i < cyc.size(); i++) {
            int a = cyc[i];                           // สะพานหมายเลข a คือเส้นที่ออกจากเกาะ a
            auto p1 = farthest(a, alive, a);          // ตัดสะพานนั้นแล้วหาเส้นผ่านศูนย์กลางของต้นไม้
            auto p2 = farthest(p1.first, alive, a);
            best = max(best, p2.second);
        }
        ans += best;
    }
    printf("%lld\n", ans);
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n; if(scanf("%d",&n)!=1) return 0;
    vector<int> f(n+1),L(n+1),indeg(n+1,0);
    for(int i=1;i<=n;i++){ scanf("%d %d",&f[i],&L[i]); indeg[f[i]]++; }
    vector<ll> t1(n+1,0),t2(n+1,0);                  // สองกิ่งที่ลึกที่สุดของแต่ละปม
    vector<int> q; q.reserve(n);
    for(int i=1;i<=n;i++) if(!indeg[i]) q.push_back(i);
    for(size_t h=0;h<q.size();h++){                  // ปอกใบทิ้งทีละชั้น เหลือไว้แต่ปมบนวง
        int u=q[h],p=f[u]; ll v=t1[u]+L[u];
        if(v>t1[p]){ t2[p]=t1[p]; t1[p]=v; } else if(v>t2[p]) t2[p]=v;
        if(--indeg[p]==0) q.push_back(p);
    }
    vector<int> comp(n+1,-1); vector<ll> res;
    vector<char> done(n+1,0);
    vector<int> cyc; vector<ll> d,P; vector<int> W;
    for(int s=1;s<=n;s++){
        if(indeg[s]==0||done[s]) continue;
        int id=(int)res.size(); cyc.clear();
        for(int u=s; !done[u]; u=f[u]){ done[u]=1; cyc.push_back(u); comp[u]=id; }
        int c=(int)cyc.size();
        d.assign(c,0); W.assign(c,0);
        for(int i=0;i<c;i++){ d[i]=t1[cyc[i]]; W[i]=L[cyc[i]]; }
        P.assign(2*c,0);
        for(int i=1;i<2*c;i++) P[i]=P[i-1]+W[(i-1)%c];
        ll local=0; deque<int> dq;                   // หน้าต่างเลื่อน หาค่ามากสุดของ d[i]-P[i]
        for(int j=0;j<2*c;j++){
            while(!dq.empty() && dq.front()<j-(c-1)) dq.pop_front();
            if(!dq.empty()) local=max(local, d[j%c]+P[j] + d[dq.front()%c]-P[dq.front()]);
            ll cur=d[j%c]-P[j];
            while(!dq.empty() && d[dq.back()%c]-P[dq.back()]<=cur) dq.pop_back();
            dq.push_back(j);
        }
        res.push_back(local);
    }
    for(int h=(int)q.size()-1;h>=0;h--) comp[q[h]]=comp[f[q[h]]];   // แจกหมายเลขกลุ่มลงต้นไม้ที่ห้อยอยู่
    for(int u=1;u<=n;u++) res[comp[u]]=max(res[comp[u]],t1[u]+t2[u]);
    ll ans=0; for(ll v:res) ans+=v;
    printf("%lld\n",ans);
}

    // ... ปอกใบ เก็บ t1/t2 และหาคำตอบฝั่งที่ข้ามวงมาเรียบร้อยแล้ว ...

    for(int h=(int)q.size()-1;h>=0;h--) comp[q[h]]=comp[f[q[h]]];   // แจกหมายเลขกลุ่มลงต้นไม้ที่ห้อยอยู่

    ll best=0;
    for(int u=1;u<=n;u++) best=max(best,t1[u]+t2[u]);   // เส้นทางที่จมอยู่ในต้นไม้ห้อย คิดถูกแล้ว
    (void)best;                                        // <-- บรรทัดที่ผิด: คิดเสร็จแล้วทิ้ง ไม่ได้เอาไปสู้กับ res เลย

    ll ans=0; for(ll v:res) ans+=v;                    // res มีแต่คำตอบฝั่งที่ข้ามวง
    printf("%lld\n",ans);
}

6
3 3
6 3
6 3
6 10
4 5
2 1