[HOJ 247][IOI 2008] Islands

作法：

首先當然是把所有連通塊分開看，這題簡單來說就是要找水母圖上的最長路（無向的），我們先找出這張水母圖的圈在哪裡，找法從隨便一個點開始沿著他唯一連出去的邊一直走，走到重複的點為止，就找到一個圈了。水母圖上的最長路分兩種，一種是沒有經過圈上的邊的，一種則是有的。對於前者，我們可以枚舉水母圈上的點，考慮這個點連往非水母圈的邊的那些點們，會形成一棵子樹，對這個子樹求最長路徑就可以了。至於經過水母圈上的邊的路徑，因為顯然如果我們已經決定好路徑和水母圈的交集的兩端點的話，剩下就取這個端點往他的子樹方向走過去的最長路就可以了，因此在回傳子樹內部的最長路時要順便回傳子樹根往下走的最長路。於是我們現在有圈上每個點往樹方向走下去的最長路了（以下稱為$val$值），還有圈上每條邊的長度，要求的是「兩點之間的距離$+$兩點的$val$值」的最大值。考慮把圈壓成序列，也就是如果原本圈上的點為$A_1,...,A_k$，考慮序列$A_1,...,A_k,A_{k+1},...,A_{2k-1}$，其中$A_{i+k}=A_i$，並且相鄰點的距離就和原本圈上連接這兩點的距離相等，記$dis[i]$代表$A_1$往右走到$A_i$的距離，和$val[i]$代表$A_i$的 val 值（最長路長），那麼我們要求的東西就是：$(i,j)$滿足$dis[i]-dis[j]+val[i]+val[j]$最大，其中$i-j<k$。因此當固定$i$的時候，我們需要的東西就會是$max\{ val[j]-dis[j] \}$，其中$j=i-k+1,...,i-1$。於是這就可以用 deque 優化在線性的時間內求出來了。

最後我傳上去 MLE 了，載測資來看發現那兩筆是DFS會到$10^6$層左右的，後來我把DFS改成自己用 stack 作才過的，感覺 IOI 沒必要這樣卡記憶體阿OAO......

code :

#include<bits/stdc++.h>
#define LL long long
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define F first
#define S second
using namespace std;
const int maxn=1000000+10 ;
 
struct P{int to,dis;}nex[maxn];
vector<P> v[maxn] ;
 
bool used[maxn] ;
int vis[maxn],vcnt ;
int nowid ;
LL nowM ;
pil sta[maxn] ;
void dfs(int x)
{
    int now=0,sz=0 ;
    sta[sz++]=(pil){x,0} ;
    LL dis ;
    while(now<sz)
    {
        x=sta[now].F , dis=sta[now++].S ;
        vis[x]=vcnt ;
        if(dis>nowM) nowM=dis , nowid=x ;
        for(auto i : v[x])
            if(vis[i.to]!=vcnt && !used[i.to])
            sta[sz++]=(pil){i.to,dis+i.dis} ;
    }
}
 
pll get_long(int x)
{
    used[x]=0 ; nowM=-1 ;
    pll ret ;
    vcnt++ ; dfs(x) ; ret.F=nowM ;
    nowM=-1 ; vcnt++ ; dfs(nowid) ;
    ret.S=nowM ; used[x]=1 ;
    return ret ;
}
 
bool vis0[maxn] ;
LL val[2*maxn],sum[2*maxn] ;
deque<pil> dq ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        int x,dis ; scanf("%d%d",&x,&dis) ;
        nex[i]=(P){x,dis} ;
        v[i].push_back((P){x,dis}) ;
        v[x].push_back((P){i,dis}) ;
    }
    LL Ans=0 ;
    for(int x0=1;x0<=n;x0++) if(!vis[x0])
    {
        int x=x0 ; LL ans=0 ;
        for(;!vis0[x];x=nex[x].to) vis0[x]=1 ;
        for(int y=nex[x].to;;y=nex[y].to)
        {
            used[y]=1 ;
            if(y==x) break ;
        }
        int cnt=0 ;
        for(int y=nex[x].to;;y=nex[y].to)
        {
            pll tmp=get_long(y) ;
            ans=max(ans,tmp.S) ;
            val[cnt]=tmp.F ;
            sum[cnt+1]=sum[cnt]+nex[y].dis ;
            cnt++ ; if(y==x) break ;
        }
        for(int i=cnt;i<2*cnt-1;i++)
            val[i]=val[i-cnt] , sum[i+1]=sum[i+1-cnt]+sum[cnt] ;
 
        dq.clear() ;
        for(int i=0;i<2*cnt-1;i++)
        {
            while(!dq.empty() && dq.back().F<=i-cnt)
                dq.pop_back() ;
            if(!dq.empty()) ans=max(ans,dq.back().S+val[i]+sum[i]) ;
            while(!dq.empty() && dq.front().S<=val[i]-sum[i])
                dq.pop_front() ;
            dq.push_front((pil){i,val[i]-sum[i]}) ;
        }
        Ans+=ans ;
    }
    printf("%lld\n",Ans) ;
}