某岛

… : "…アッカリ~ン . .. . " .. .
October 16, 2014

IOI 2008 D2T1 Islands

http://www.lydsy.com/JudgeOnline/problem.php?id=1791
http://www.spoj.com/OI/problems/ISLAND/

D2T1 Islands

Brief description:

给定一个树加一条边。。求这个图的最长链。

Analysis:

Codeforces Beta Round #88

一棵树加一条边就是会有一个环。。讨论最长链。。

不在环上。。那么规约到树上最长链。。
在环上。。

那么设 d[i] 表示环上某个点向下所能到达的最远点。
。。 s[i] 表示环上第 0 个结点,沿着正方向到第 i 个结点之间的距离。。。
。。dist(i, j) 表示环上两个点的最长路径。。讨论方向。。
。。有 dist(i, j) = max(s[i] – s[j], ss – (s[i] – s[j))

。。ss 表示整个环的长度。。

答案就是 max{ d[i] + d[j] + dist(i, j) | j < i }
把上式拆开。。

就是每次。。找。。

max{
d[i] + s[i] + max(d[j] – s[j]),
ss + d[i]-s[i] +max(d[j] + s[j]);
}

然后 O(n) 扫描就可以了。。。

//}/* .................................................................................................................................. */

const int N = int(1e6) + 9, M = 2*N;

LL dd[N], d[N], s[N]; int c[N]; int nn;
int Q[N], cz, op, uu;

int hd[N], prd[M], suc[M], to[M], ww[N];
int n;

#define aa to[i^1]
#define bb to[i]
#define w ww[i/2]

    inline void del(int i){
        if (hd[aa] == i) prd[hd[aa] = suc[i]] = 0;
        else suc[prd[suc[i]] = prd[i]] = suc[i];
    }

    inline void dell(int i){
        del(i), del(i^1);
    }

int vis[N]; bool st[N];
#define v (bb)

bool dfs(int u, int p = -1){ // Find_Circle
    vis[u] = 1; REP_G(i, u) if (i != p){
        if (vis[v]) st[v] = 1;
        if (vis[v] || dfs(v, i^1)){
            c[nn] = v, s[nn+1] = s[nn] + w, ++nn, dell(i);
            return !st[u];
        }
    }
    return 0;
}

LL f(int x){

    nn = 0, dfs(x); LL z = 0; REP(ii, nn){

        int s = c[ii], ss = s; dd[ii] = 0;

        cz = 0, op = 1; Q[0] = s; d[s] = 0; vis[s] = 2;

        while (cz < op){
            int u = Q[cz++]; REP_G(i, u) if (vis[v] != 2){
                d[v] = d[u] + w;
                vis[v] = 2, Q[op++] = v;

                if (d[v] > dd[ii]){
                    dd[ii] = d[v];
                    ss = v;
                }
            }
        }

        cz = 0, op = 1; Q[0] = ss, d[ss] = 0; vis[ss] = 3;

        while (cz < op){
            int u = Q[cz++]; REP_G(i, u) if (vis[v] != 3){
                d[v] = d[u] + w;
                vis[v] = 3, Q[op++] = v;

                checkMax(z, d[v]);
            }
        }
    }

#define d dd
    LL ss=s[nn],pre1=d[0]-s[0],pre2=d[0]+s[0]; FOR(i,1,nn){
        checkMax(z, d[i]+max(s[i]+pre1,ss-s[i]+pre2));
        checkMax(pre1, d[i]-s[i]), checkMax(pre2, d[i]+s[i]);
    }
    return z;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("isl19g.in", "r", stdin);
    freopen("isl5.txt", "w", stdout);
#endif

    RD(n); for (int i=2,a=1;i<=n<<1;++a){
        aa = a, RD(bb, w);
        prd[hd[aa]] = i, suc[i] = hd[aa], hd[aa] = i++;
        prd[hd[aa]] = i, suc[i] = hd[aa], hd[aa] = i++;
    }

    LL z = 0; REP_1(i, n) if (!vis[i]) z += f(i); OT(z);
}

— UPD 一发。。

const int N = int(1e6) + 9;
map<int, int> adj[N]; int fa[N], fw[N];
int dfn[N], low[N], nn;
LL f[N], z; // 不取, 取 or 不取
int n;

int q[2*N], cz, op;
void gao(int st, int ed, int ww) {
    vector<LL> C,D;
    VI tt; tt.PB(ed+1); tt.PB(st+1);
    C.PB(f[ed]); C.PB(f[st]);
    D.PB(0); D.PB(ww); D.PB(D.back()+fw[st]);

    int u = fa[st]; for (;u!=ed;u=fa[u]) {
        tt.PB(u+1); C.PB(f[u]);
        D.PB(D.back()+fw[u]);
    }
    tt.PB(u+1);
    C.PB(f[u]);

    /*REP(i, SZ(C)) {
        cout << tt[i] << " "<< C[i] << " "<< D[i] << endl;
    }
    cout << endl;*/

    LL len = D.back();
    //cout << " len: " << len << endl;

    LL ff = 0; FOR(i, 1, SZ(C)-1) checkMax(ff, C[i] + max(D[i], len-D[i]));
    checkMax(z, f[u] + ff);
    int n = SZ(C)-1; FOR(i, 1, n) {
        tt.PB(tt[i]);
        C.PB(C[i]);
        D.PB(D.back() + D[i]-D[i-1]);
    }

    /*
    REP(i, SZ(C)) {
        cout << tt[i] << " "<< C[i] << " "<< D[i] << endl;
    }
    cout << "ff" << ff << endl;*/


    int cz = 0, op = 0; q[0] = 0; FOR(i, 1, SZ(C)) {
        if (i - q[cz] >= n) ++cz;
        checkMax(z, C[i] + C[q[cz]] + (D[i] - D[q[cz]]));
        while (cz <= op && C[q[op]] - D[q[op]] <= C[i] - D[i]) --op;
        q[++op] = i;
    }
    checkMax(f[u], ff);
}

void dfs(int u = 0) {
    low[u] = dfn[u] = ++nn;
    //cout << " " << u+1 << endl;

    ECH(it, adj[u]) {
        int v = it->fi; if (v == fa[u]) continue;
        int w = it->se;

        if (!dfn[v]) {
            fa[v] = u; fw[v] = w; dfs(v);
            checkMin(low[u], low[v]);
        } else {
            checkMin(low[u], dfn[v]);
        }

        //cout << u+1 << " " << v+1 << " " << dfn[u] << " " << low[v] << endl;

        if (dfn[u] < low[v]) {
            //cout << " !! " << u+1 <<  " " << v+1 << " " << f[u] << " "<< f[v] << " " << w << endl;
            checkMax(z, f[u] + f[v] + w);
            checkMax(f[u], f[v] + w);
        } else if (fa[v] != u && dfn[u] < dfn[v]) {
            //cout << " CC " << u+1 <<  " " << v+1 << " " << f[u] << " "<< f[v] << " " << w << endl;
            gao(v, u, w);
        }
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n); REP(u, n) {
        int p, w; RD(p, w); --p;
        checkMax(adj[p][u], w);
        checkMax(adj[u][p], w);
    }

    LL ans = 0; REP(i, n) if (!dfn[i]) {
        nn = 0; z = 0; dfs(i);
        ans += z;
        //cout << z << endl;
    }
    cout << ans << endl;
}