自动搬运

查看原文

来自洛谷，原作者为

	TEoS 水平不够运气来凑

搬运于2025-08-24 21:59:34，当前版本为作者最后更新于2019-06-25 17:09:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一道不错的题目，思路比较灵活，但码量不大，在现在的时空限制下也基本不会出现被卡的情况，总体还是很好的。

当时看到题目的颜色我就**了，刚开始没有思路，想参考题解又发现大佬们要么讲得十分深奥要么讲得十分简略，不过后来有了思路之后写起来也不会太难。所以我就写一篇自认为浅显易懂的题解吧。

可能和有些大佬实现方法相同，不过我会尽可能讲得清晰的！

---

实现流程：dfs+树形DP+单调队列

思路：

由于这个公园有$N$座岛屿和$N$座桥，就相当于一个由$N$个节点和$N$条边构成的无向图。显然，这样的一个无向图就是一个基环树森林。

因此，根据题意，要使经过的总路径最长且每棵基环树都只能经过一次，显然答案就是每棵基环树的最长链，或者也可以叫直径的和。如何求基环树的直径呢？和求树的直径类似，只不过要多考虑这个环罢了。对于每个基环树，我们先把这个环看做一个整体并作为这棵基环树的根节点，就成为了一棵普通的树，之后再对环进行讨论。基环树的直径显然有下面两种可能：

1. 在“根节点”的某一棵子树中
2. 经过“根节点”，在“根节点”的某两棵子树中

对于上面的两种情况，我们分类讨论，最后取大的答案就可以了。在处理这些之前，应该先找出当前基环树的环，这步用dfs实现就可以。找出来后，将它们作上标记，方便之后的操作。

对于第一种情况，我们对“根节点”的每棵子树单独讨论，求每棵子树的直径，取其中最大的答案就可以了。“根节点”的每棵子树也就是以环上的每个节点为根的子树。这步可以用树形DP来解决，并且在解决这种情况的同时，还能处理出以环上每个节点为起点，走向以其为根的子树，能够到达的最远距离，为处理下一种情况做准备。这里将这个数据存入$d$数组，即$d_i$代表$i$节点对应的值。注意，为了方便，在之前找出环并标记之后，环上的节点都以在环上的次序命名，即$i$节点实际对应的是环上的第$i$个

对于第二种情况，显然对于这种情况，我们需要找到环上的两个节点$i,j$，使得$d_i+d_j+dist_{i,j}$最大，其中$dist_{i,j}$表示节点$i,j$在环上的距离。如果一个个枚举的话，显然时间复杂度太大，不可行。这里可以断开环将断开后的链复制到两倍的长度，用单调队列进行优化，在下面会进行详细讲解。

上面的思路可能讲得比较笼统，如果没看懂可以接下去看。

下面给出具体实现流程。

---

具体实现流程：

1、输入

输入就是最普通的邻接表存图，就不多说了，直接上代码。

输入代码：

ll n,tot;
ll edge[2*N],head[N],ver[2*N],Next[2*N];

il void add(int x,int y,int z)
{
    edge[++tot]=z,ver[tot]=y,Next[tot]=head[x],head[x]=tot;
}//邻接表插入

cin>>n;
for(int i=1;i<=n;i++)
{
    int y,z;
    scanf("%d %d",&y,&z);
    add(i,y,z);
    add(y,i,z);//无向边成对存储
}

---

2、dfs找环

就是基本的深搜，深搜的同时标记是否走过，走到走过的节点即为找到了环，在这里我们把这个节点叫做环的衔接点。如何剔出这个环呢？在这里定义一个bool类型的dfs函数，当找到环时返回值为1，回溯时一直到第三次走到衔接点时，将返回值恢复为0，就可以解决这个问题。

我们要对环上的节点存储一些信息。我们将环的衔接点定为$1$号节点，按回溯方向依次为$2,3,...,n$号节点，表示这个环由$n$个节点组成。对于$i$号节点，该节点的原始编号，即输入时的编号为$x$，我们要存储以下信息：

• $v_x=1$，表示这个节点在dfs时被走过了。特别的，若该节点是环的衔接点，则令$v_x=2$，用来辨识衔接点。这个标记在dfs时走过的所有节点都要做。
• $v2_x=1$，表示这个节点所在的基环树已经走过了。这个标记之后所有节点都要做，目的是判断一棵基环树是否走过，在这里先给环上的点标记是为了后面方便。
• $r_i=x$，表示环上的$i$号节点的原始编号为$x$。
• $s_i=s_{i-1}+dist_{i-1,i}$，此时$dist_{i-1,i}$就等于当前遍历到的边的长度。特别的，由于后面的操作要断环并复制链，复制$s$数组时为了保证复制数据的正确性，要在$0$号位置存储一个数据，使得$s_0=s_1-dist_{0,1}$。这个步骤到后面复制的时候可以更好的理解。

这里有一个问题，为什么还要额外开一个$v2$数组来判定是否走过呢？因为在$v$数组只是用来判定dfs时是否走过，而dfs时并不是所有节点都会被遍历到，而$v2$数组在之后的操作中可以保证每个节点都被遍历到，因此可以作为一棵基环树是否走过的依据。

在dfs时还有一个点要注意，因为遍历时要保证走向的下一个节点不是上一个节点，因此我们要对此进行特判。怎么特判呢？原来我有一个想法，存储上一个节点的编号，保证不再走到这个节点。然而看了样例之后我就把这个想法否决了（这个样例真的良心，自己看看就知道原因了）。于是只能把思路往边上放。

众所周知，邻接表存无向图时是将同一条边拆作两条有向边分开存的，而指向这两条有向边的指针的数值是相邻的，并且其中偶数较大，奇数较小。利用这个特点，我们就可以判断当前循环到的边是否是刚刚走过的这条边。操作如下：

if(i!=((la-1)^1)+1)//la指向刚刚走过的那条边，i指向现在循环到的这条边
//当这个条件成立时，说明当前循环到的边不是刚刚走过的那条边
//((x-1)^1)+1，指向与x相邻的数y，并且x,y中偶数较大。例如，若x=3，则y=4；若x=4，则y=3。
//原理请读者自己思考

dfs找环代码：

ll cnt;
ll v[N],v2[N],r[N],s[N];

il bool dfs(int now,int la)
{
    if(v[now]==1)
    {
        v[now]=2,r[++cnt]=now,v2[now]=1;
        return 1;//返回值改为1
    }//找到衔接点
    v[now]=1;//维护访问数组
    for(int i=head[now];i;i=Next[i])
        if(i!=((la-1)^1)+1 && dfs(ver[i],i))//如果当前边不是上一条边并且当前节点在环上
        {
            if(v[now]!=2)//当前节点不是衔接点
                r[++cnt]=now,v2[now]=1,s[cnt]=s[cnt-1]+edge[i];
            else//是衔接点
            {
                s[st-1]=s[st]-edge[i];
                return 0;//返回值改为0
            }
            return 1;//返回1
        }
    return 0;	
}

---

3、处理第一种情况

对于环上的每个节点，求以其为根的子树的直径。这就是求树的直径的模板问题了，用树形DP就可以解决，不懂的可以点击食用，这里就不赘述了。

对于代码有一点要说明的，因为在这里$cnt$的计算是没有重置的，因此会一直加下去，所以在dp前要先存储起始值。

处理第一种情况代码：

ll ans,ans2;//ans存储当前子树的直径，ans2存储第一种情况的答案
ll d[N];

st=cnt+1,ans2=0;
il void tree_dp(int now)
{
    v2[now]=1;
    for(int i=head[now];i;i=Next[i])
    {
        int y=ver[i];
        if(v2[y])
            continue;
        tree_dp(y);
        ans=max(ans,d[now]+d[y]+edge[i]);
        d[now]=max(d[now],d[y]+edge[i]);
    }
}//树形DP求树的直径

for(int i=st;i<=cnt;i++)
{
    ans=0;//初始化
    tree_dp(r[i]);
    ans2=max(ans2,ans);//找出最大的答案
}

---

4、处理第二种情况

找出满足$d_i+d_j+dist_{i,j}$最大的$i,j$，枚举显然会超时。对于这类环形问题，有一种比较常用的做法就是从某个点断开环并复制为一条两倍长度的链。复制过程只要将一些关键信息再存一遍就可以了。于是问题可以等价为：在一条长度$2n$的链上，找到两个满足$abs(i-j)\leq n$的节点$i,j$，使得$d_i+d_j+dist_{i,j}$最大。

这个问题是不是一脸可以用单调队列优化的亚子？要你寡 根据单调队列的思想，及时排除一定不是最优的决策。因为要找的是最大的$d_i+d_j+dist_{i,j}$，其中$dist_{i,j}$即为$s_i-s_j(j<i)$。整理后即为：$d_i+s_i+d_j-s_j$。

对于每个节点$i$，显然如果一个节点$j(j<i)$满足$d_j-s_j\leq d_i-s_i$，那么根据最优性，$j$是一定不会被选作最终决策的，因此可以将其从答案队列中删除。讲到这里，实现起来就很简单了。

对于代码有一点要说明的，因为$cnt$没有重置，根据定义环上节点的数量为$cnt-st+1$，因此断环复制后的节点范围即为$st~cnt+cnt-st+1$。这样，节点$i$对应的另一个节点即为$i+cnt-st+1$。

处理第二种情况代码：

int ans3;
ll dp[2*N];

ans3=0;
for(int i=st;i<=cnt;i++)
{
    dp[i+cnt-st+1]=dp[i]=d[r[i]]; 
    s[i+cnt-st+1]=s[i+cnt-st]+s[i]-s[i-1]; //和第2步递推s数组同理，s[i]-s[i-1]即为两点之间的距离
}//复制环
deque<int> q;
for(int i=st;i<=2*cnt-st+1;i++)//对复制后的链进行遍历
{
    while(q.size() && q.front()<=i-cnt+st-1)
        q.pop_front();//排除超出范围的决策
    if(q.size()) 
        ans3=max(ans3,dp[i]+dp[q.front()]+s[i]-s[q.front()]);//更新答案
    while(q.size() && dp[q.back()]-s[q.back()]<=dp[i]-s[i])
        q.pop_back();//排除过时的决策
 	q.push_back(i);//将当前决策插入队列
}

---

这样就结束了，也不会太复杂吧。

最后奉上完整代码：

#include<iostream>
#include<cstdio>
#include<queue>
#define ll long long
#define il inline
using namespace std;
const int N=1e6+100;
ll n,tot=0,cnt,ans,anss,st,ans2,ans3;
ll edge[2*N],head[N],ver[2*N],Next[2*N];
ll v[N],v2[N],r[N],d[N],dp[2*N],s[N];
il void add(int x,int y,int z)
{
    edge[++tot]=z,ver[tot]=y,Next[tot]=head[x],head[x]=tot;
}
il bool dfs(int now,int la)
{
    if(v[now]==1)
    {
        v[now]=2,r[++cnt]=now,v2[now]=1;
        return 1;
    }
    v[now]=1;
    for(int i=head[now];i;i=Next[i])
        if(i!=((la-1)^1)+1 && dfs(ver[i],i))
        {
            if(v[now]!=2)
                r[++cnt]=now,v2[now]=1,s[cnt]=s[cnt-1]+edge[i];
            else
            {
                s[st-1]=s[st]-edge[i];
                return 0;
            }
            return 1;
        }
    return 0;		
}//2、dfs找环
il void tree_dp(int now)
{
    v2[now]=1;
    for(int i=head[now];i;i=Next[i])
    {
        int y=ver[i];
        if(v2[y])
            continue;
        tree_dp(y);
        ans=max(ans,d[now]+d[y]+edge[i]);
        d[now]=max(d[now],d[y]+edge[i]);
    }
}//3、处理第一种情况
il ll brt(int root)
{
    st=cnt+1,ans2=0,ans3=0;
    dfs(root,0);
    for(int i=st;i<=cnt;i++)
    {
        ans=0;
        tree_dp(r[i]);
        ans2=max(ans2,ans);
        dp[i+cnt-st+1]=dp[i]=d[r[i]];
        s[i+cnt-st+1]=s[i+cnt-st]+s[i]-s[i-1];
    }
    deque<int> q;
    for(int i=st;i<=2*cnt-st+1;i++)
    {
        while(q.size() && q.front()<=i-cnt+st-1)
            q.pop_front();
        if(q.size()) 
            ans3=max(ans3,dp[i]+dp[q.front()]+s[i]-s[q.front()]);
        while(q.size() && dp[q.back()]-s[q.back()]<=dp[i]-s[i])
            q.pop_back();
        q.push_back(i);
    }//4、处理第二种情况
    return max(ans2,ans3);//取大的答案
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int y,z;
        scanf("%d %d",&y,&z);
        add(i,y,z);
        add(y,i,z);
    }//1、输入
    for(int i=1;i<=n;i++)
        if(!v2[i])//如果没走过就走
            anss+=brt(i);//加上答案
    cout<<anss;
    return 0;
}

该讲的都讲得很清楚了，完整代码里就不再注释了。

---

希望对大家有帮助，有不足之处请指出。