P4381 [IOI2008]Island
一道不错的题目，思路比较灵活，但码量不大，在现在的时空限制下也基本不会出现被卡的情况，总体还是很好的。
当时看到题目的颜色我就**了，刚开始没有思路，想参考题解又发现大佬们要么讲得十分深奥要么讲得十分简略，不过后来有了思路之后写起来也不会太难。所以我就写一篇自认为浅显易懂的题解吧。
可能和有些大佬实现方法相同，不过我会尽可能讲得清晰的！
实现流程：dfs+树形DP+单调队列
思路：
由于这个公园有
因此，根据题意，要使经过的总路径最长且每棵基环树都只能经过一次，显然答案就是每棵基环树的最长链，或者也可以叫直径的和。如何求基环树的直径呢？和求树的直径类似，只不过要多考虑这个环罢了。对于每个基环树，我们先把这个环看做一个整体并作为这棵基环树的根节点，就成为了一棵普通的树，之后再对环进行讨论。基环树的直径显然有下面两种可能：
- 在“根节点”的某一棵子树中
- 经过“根节点”，在“根节点”的某两棵子树中
对于上面的两种情况，我们分类讨论，最后取大的答案就可以了。在处理这些之前，应该先找出当前基环树的环，这步用dfs实现就可以。找出来后，将它们作上标记，方便之后的操作。
对于第一种情况，我们对“根节点”的每棵子树单独讨论，求每棵子树的直径，取其中最大的答案就可以了。“根节点”的每棵子树也就是以环上的每个节点为根的子树。这步可以用树形DP来解决，并且在解决这种情况的同时，还能处理出以环上每个节点为起点，走向以其为根的子树，能够到达的最远距离，为处理下一种情况做准备。这里将这个数据存入
对于第二种情况，显然对于这种情况，我们需要找到环上的两个节点
上面的思路可能讲得比较笼统，如果没看懂可以接下去看。
下面给出具体实现流程。
具体实现流程：
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，就可以解决这个问题。
我们要对环上的节点存储一些信息。我们将环的衔接点定为
这里有一个问题，为什么还要额外开一个
在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就可以解决，不懂的可以点击食用，这里就不赘述了。
对于代码有一点要说明的，因为在这里
处理第一种情况代码：
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、处理第二种情况
找出满足
这个问题是不是一脸可以用单调队列优化的亚子？要你寡 根据单调队列的思想，及时排除一定不是最优的决策。因为要找的是最大的
对于每个节点
对于代码有一点要说明的，因为
处理第二种情况代码：
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;
}该讲的都讲得很清楚了，完整代码里就不再注释了。
希望对大家有帮助，有不足之处请指出。