# 某岛

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

## D2T1 Islands

### Analysis:

Codeforces Beta Round #88

。。 s[i] 表示环上第 0 个结点，沿着正方向到第 i 个结点之间的距离。。。
。。dist(i, j) 表示环上两个点的最长路径。。讨论方向。。
。。有 dist(i, j) = max(s[i] – s[j], ss – (s[i] – s[j))

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

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

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

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;
}
```