---

Island(IOI 2008)

Description

你准备浏览一个公园，该公园由 N 个岛屿组成，当地管理部门从每个岛屿 i 出发向另外一个岛屿建了一座长度为 L_i 的桥，不过桥是可以双向行走的。同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。相对于乘船而言，你更喜欢步行。你希望经过的桥的总长度尽可能长，但受到以下的限制：

• 可以自行挑选一个岛开始游览。
• 任何一个岛都不能游览一次以上。
• 无论任何时间，你都可以由当前所在的岛 S 去另一个从未到过的岛 D。从 S 到 D 有如下方法：
  • 步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离中。
  • 渡船：你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 SS 走到 D (当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛)。

注意，你不必游览所有的岛，也可能无法走完所有的桥。

请你编写一个程序，给定 N 座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的长度之和的最大值。

Input Format

第一行包含 N 个整数，即公园内岛屿的数目。

随后的 N 行每一行用来表示一个岛。第 i 行由两个以单空格分隔的整数，表示由岛 i 筑的桥。第一个整数表示桥另一端的岛，第二个整数表示该桥的长度 L_i。你可以假设对于每座桥，其端点总是位于不同的岛上。

Output Format

仅包含一个整数，即可能的最大步行距离。

Sample Input

73 87 24 21 41 93 42 3

Sample Output

24

解析

很多年前的一道老题了，题意即为：给定基环树森林，求各棵基环树的直径之和。

大体思路是这样的，对于每一颗基环树，可以先找到基环树的环\(loop_{1-k}\)，设以\(loop_i\)为根的树中，以\(loop_i\)为起点的最长链长度为\(deep_i\)，该树中的朴素直径为\(diameter_i\)，那么这一棵基环树的答案一定就是：

\[ ans=\max \begin{cases} \max\{diameter_i\} \\ \max\{deep_i+deep_j+path(loop_i,loop_j)\} \end{cases} \]

对于第一个式子，我们直接用树形\(DP\)求树的直径即可。

对于第二个式子，\(deep\)我们显然可以直接\(dfs\)处理，然后我们断环为链并复制一倍，\(path(loop_i,loop_j)\)的长度我们可以改为\(sum_j-sum_i\)，那么就是求

\[ \max_{i < j}\{deep_i+deep_j+sum_j-sum_i\} \]

把它当做\(DP\)，枚举\(j\)，单调队列维护\({deep_i-sum_i}\)单调性即可。

然后累加每一棵基环树的答案即可。

我的做题历程和一些我犯过的错误：

• 单调队列误解，用了单调栈
• 没有考虑二元环的情况，环上边权选择重复，需要特判
• 发现做动态规划不能遍历每一种情况，断环为链时需要将链复制放在原链的后面，在做动态规划才能遍历每一种情况，需要顺带改进单调队列，距离当前长度超过\(n\)时弹出队首
• 发现菊花图的情况很容易被卡，是因为没有判断之间以环上某一个点为根取该树的直径的情况，对于环上每一个点，做一遍\(DP\)找以该节点为根的树的直径，最后以最大值和原答案取\(max\)
• 没有对每一棵基环树中子树的朴素直径与\(DP\)得到的答案取\(max\)，对于每一棵基环树，应该都取一个\(max\)来累加答案，而非放在最后取

然后就是还有一个点是被卡常的，至于怎么办，我也不知道。

\(Code:\)

#include
    
     #define mset(name,val) memset(name,val,sizeof name)using namespace std;const int N=1e6+10;const long long INF=LONG_LONG_MAX;int n,Last[N*2],t;long long ans,deep[N*2],Link[N*2],sum[2*N],f[N*2],ans_,F[N],D[N];int dfn[N],a[N*2],loop[N],inloop[N],tot,cnt,fa[N],used[N],vis[N];struct edge{int ver,next;long long val;}e[N*2];inline void insert(int x,int y,long long v){    e[++t].val=v;e[t].ver=y;e[t].next=Last[x];Last[x]=t;}inline char Getchar(){     static char buf[100000],*p1=buf,*p2=buf;     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; }inline void readll(long long &k){    long long x=0,w=0;char ch;    while(!isdigit(ch))w|=ch=='-',ch=Getchar();    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=Getchar();    k=(w?-x:x);}inline void read(int &k){    int x=0,w=0;char ch;    while(!isdigit(ch))w|=ch=='-',ch=Getchar();    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=Getchar();    k=(w?-x:x);}inline void input(void){    read(n);    for(register int i=1;i<=n;i++)    {        int y;long long v;        read(y);readll(v);        insert(i,y,v);        insert(y,i,v);    }}inline void reset(void){    mset(loop,0);    mset(inloop,0);    mset(Link,0);    mset(deep,0);    mset(a,0);    tot=0;cnt=0;ans_=0;}inline void find_loop(int u){    dfn[u]=++cnt;    for(register int i=Last[u];i;i=e[i].next)    {        int v=e[i].ver;        if(v==fa[u])continue;        if(dfn[v])        {            if(dfn[v]
     
      2)    {        for(register int i=1;i<=tot;i++)        {            for(register int j=Last[loop[i]];j;j=e[j].next)            {                if((e[j].ver==loop[i-1]&&i>1)||(e[j].ver==loop[tot]&&i==1))                {                    Link[i]=e[j].val;                    a[i]=loop[i];                }            }        }    }    else    {        long long v1=0,v2=0;        for(register int i=Last[loop[1]];i;i=e[i].next)        {            if(e[i].ver==loop[2])            {                if(!v1)v1=e[i].val;                else                {                    v2=e[i].val;                    break;                }            }        }        Link[1]=v1;Link[2]=v2;        a[1]=loop[1];a[2]=loop[2];     }    for(register int i=tot+1;i<=2*tot;i++)    {        Link[i]=Link[i-tot];        a[i]=a[i-tot];        deep[i]=deep[i-tot];    }    for(register int i=1;i<=tot*2;i++)        sum[i]=sum[i-1]+Link[i];}inline long long calc(int x){    return deep[x]-sum[x];}inline long long dp(void){    deque < int > q;long long res=ans_;    q.push_back(1);res=max(res,deep[1]);    for(register int j=2;j<=2*tot;j++)    {        while(!q.empty()&&j-q.front()>=tot)q.pop_front();        f[j]=sum[j]+deep[j]+calc(q.front());        while(!q.empty()&&calc(q.back())
     
    

---