(IOI) 2008 Day 1 p2 Islands

https://contest.yandex.com/ioi/contest/567/problems/B/

剛好之前在TIOJ寫過(?

每個連通塊的答案有兩種，一種是不經過環的，一種是經過環的。

對於沒有經過環的，好好DP一下就好(? (隨時維護最長鍊並且更新(?))

對於有經過環的，是個deque優化的DP (?)

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL,int> pii;
const int N = 1000006;

#define F first
#define S second

#define SZ(x) ((int)(x).size())

vector<pii> G[N];

char vis[N];

LL dp[N];

vector<int> v;

int deg[N];

void get_all(int now)
{
    vis[now] = true;
    v.push_back(now);
    for (pii p:G[now])
    {
        if (!vis[p.F])
        {
            get_all(p.F);
        }
    }
}

int id[2*N];
int len[2*N];
LL pre[2*N];

LL solve(int x)
{
    v.clear();
    get_all(x);
    queue<int> que;
    LL ret=0;
    for (int i:v)
    {
        if (deg[i] == 1)
        {
            que.push(i);
        }
    }
    while (!que.empty())
    {
        int t=que.front();
        que.pop();
        vis[t] = 2;
        for (pii p:G[t])
        {
            if (vis[p.F] == 2) continue;
            ret = max(ret,dp[p.F] + dp[t] + p.S);
            dp[p.F] = max(dp[p.F],dp[t] + p.S*1LL);
            deg[p.F]--;
            if (deg[p.F] == 1) que.push(p.F);
        }
    }
    vector<int> cycle;
    for (int i:v)
    {
        ret = max(ret,dp[i]);
        if (vis[i] == 1 && SZ(cycle) == 0)
        {
            int now=i;
            bool chg = false;
            do {
                cycle.push_back(now);
                //cout << "before now = " << now << " , ";
                vis[now] = 3;
                chg = false;
                //cout << "vis = " << vis[now] << endl;
                for (pii p:G[now])
                {
                    if (vis[p.F] == 1)
                    {
                        now = p.F;
                        chg = true;
                        break;
                    }
                }
                //cout << "after now = " << now << endl;
            } while (now != i && chg);
        }
    }
    //cout << "x = " << x << " , sz cycle = " << SZ(cycle) << endl;
    if (SZ(cycle) == 2)
    {
        for (int i:cycle)
        {
            for (pii p:G[i])
            {
                if (vis[p.F] == 3)
                {
                    ret = max(ret,dp[i] + dp[p.F] + p.S);
                }
            }
        }
        return ret;
    }
    int n = SZ(cycle);
    cycle.push_back(cycle[0]);
    for (int i=0;n>i;i++)
    {
        id[i+1] = cycle[i];
        for (pii p:G[ cycle[i] ])
        {
            if (p.F == cycle[i+1])
            {
                len[i+1] = p.S;
                break;
            }
        }
    }
    for (int i=1;n>=i;i++)
    {
        //cout << "i = " << i << " , id = " << id[i] << " , len = " << len[i] << endl;
        //dp_id[i] = dp[ id[i] ];
        id[i+n] = id[i];
        len[i+n] = len[i];
        //dp_id[i+n] = dp_id[i];
    }
    for (int i=1;2*n>=i;i++)
    {
        pre[i] = pre[i-1] + len[i];
    }
    deque<pii> dq;
    //pii --> value(dp_id[id]), id
    for (int i=1;2*n>=i;i++)
    {
        if (SZ(dq) == 0)
        {
            ret = max(ret,dp[ id[i] ]);
        }
        else
        {
            while ( SZ(dq) && dq.front().S <= i-n) dq.pop_front();
            ret = max(ret,dp[ id[i] ] + dq.front().F + pre[i-1] - pre[ dq.front().S-1 ]);
        }
        pii now = make_pair(dp[ id[i] ],i);
        while (SZ(dq) && pre[i-1] - pre[ dq.back().S-1 ] + dq.back().F <= now.F) dq.pop_back();
        dq.push_back(now);
    }
    return ret;
}

int main ()
{
    int n;
    scanf("%d",&n);
    for (int i=1;n>=i;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        deg[x]++;
        deg[i]++;
        G[x].push_back(make_pair(i,y));
        G[i].push_back(make_pair(x,y));
    }
    LL ans=0;
    for (int i=1;n>=i;i++)
    {
        if (!vis[i])
        {
            ans += solve(i);
        }
    }
    printf("%lld\n",ans);
}