IOI 2008

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

D2T1 Islands

Brief description:

給定一個樹加一條邊。。求這個圖的最長鏈。

Analysis:

http://www.shuizilong.com/house/archives/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) 掃描就可以了。。。 [cpp] //}/* .................................................................................................................................. */ 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); } [/cpp]