『Island 基环树直径』

<更新提示>

<第一次更新>

<正文>

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

7
3 8
7 2
4 2
1 4
1 9
3 4
2 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<bits/stdc++.h>
#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]<dfn[u])continue;
            loop[++tot]=v,inloop[v]=true;
            for(;v!=u;v=fa[v])
                loop[++tot]=fa[v],inloop[fa[v]]=true;
        }
        else fa[v]=u,find_loop(v);
    }
}
inline long long dfs(int x)
{
    long long res=0;
    used[x]=true;
    for(register int i=Last[x];i;i=e[i].next)
    {
        int y=e[i].ver;
        if(!used[y]&&!inloop[y])
            res=max(res,dfs(y)+e[i].val);
    }
    return res;
}
inline void find_diameter(int x)
{
    vis[x]=true;
    for(register int i=Last[x];i;i=e[i].next)
    {
        int y=e[i].ver;
        if(!vis[y]&&!inloop[y])
        {
            find_diameter(y);
            F[x]=max(F[x],D[x]+D[y]+e[i].val);
            D[x]=max(D[x],D[y]+e[i].val);
        }   
    }
    ans_=max(ans_,F[x]);
}
inline void get_deep(void)
{
    for(register int i=1;i<=tot;i++)
    {
        deep[i]=dfs(loop[i]);
        find_diameter(loop[i]);
    } 
}
inline void init(void)
{
    if(tot>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())<calc(j))q.pop_back();
        q.push_back(j);
        res=max(res,f[j]);
    } 
    return res;
}
int main(void)
{
    input();
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            reset();
            find_loop(i);
            get_deep();
            init();
            ans+=dp();
        }
    }
    printf("%lld\n",ans);
    return 0;
}

<后记>