算是较难的一道基环树模板题

题意简明扼要,有一堆基环树构成了基环树森林,需求所有基环树的直径之和。

基环树定义:一棵树有$n$个节点$n$条边

显然一棵普通的树有$n$个节点$n-1$条边,那么基环树就是在普通的树的基础上多加了一条边,这条边必然会形成一个环。

所以基环树相对于树来讲就是多了一个环的处理。

基环树的直径求法:

首先肯定要找到环上的所有节点,就是相当于无向图找环。大致上常用的有拓扑排序和$dfs$,$tarjan$也可以。(我使用了$dfs$找环

$dfs$在无向图上找环比较麻烦,它只能处理环的变数$>2$的环,所以$=2$的环还要进行特判。(大体来说就是$num$从$1$开始建边这样一条边的反向边就是$i\oplus1$,这样特判一下就好了。

找到环后,通过对一些例子的手玩,不难发现基环树直径的构成情况:

$1.$就是不在环上的节点组成的最长链。
$2.$由环上两点及分别以他们为根的子树中的经过根的最长链构成。

对第一种情况我们开一个数组记录哪些点在环上,对环上每个点分别跑一遍最长链的$dp$并同时更新$answer$即可。如果他的儿子在环上就$continue$。跑完之后再开一个数组记录经过根的最长链。

(最长链$dp$就是对每个节点求出以他为根的子树且经过他的最长链和次长链,每求完一个节点的信息就对$answer$进行更新。

对于环上的两点之间的距离,可能是顺时针也可能是逆时针。所以需要破环成链,这样每个节点都会被逆时针顺时针走一遍。求出一个距离前缀数组,两点之间差值即为环上距离。

那么现在可以写出$dp$式子$answer=max(answer,d[i]+d[j]+dis[i]-dis[j])$

这个$dp$式子的与i有关和与j有关的项是独立的,所以可以单调队列优化。

对于每个节点找到他之前的$d[j]-dis[j]$最大的$j$更新即可

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
#define int long long
#define N 1000050
int head[N],num=1,n,vis[N],ins[N],stack[N],top,circle[N],cnt,flag,zongshu,huan[N],q[N*2],ooo,tmp;
ll ans,answer,dis[N*2],dp[N][2],d[N*2];
struct node
{
    int next,to;
    ll dis;
}edge[N*2];
void addedge(int u,int v,ll w)
{
    edge[++num]=(node){head[u],v,w};
    head[u]=num;
}
void dfs(int x,int fa)
{
    ins[x]=1,stack[++top]=x;
    for(register int i=head[x];i;i=edge[i].next)
    {
        if(flag)return;
        int v=edge[i].to;
        if(v==fa)continue;
        if(ins[v])
        {
            flag=1;circle[++cnt]=v;huan[v]=1;
            while(stack[top]!=v)
                huan[stack[top]]=1,circle[++cnt]=stack[top--];
            return;
        }
        dfs(v,x);
    }
    top--;ins[x]=0;
}
void dfs2(int x,int fa)
{
    if(!vis[x])zongshu++,vis[x]=1;
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa)continue;
        if(!vis[v])dfs2(v,x);
    }
}
void dpp(int x,int fa)
{
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa || huan[v])continue;
        dpp(v,x);
        if(dp[v][0]+edge[i].dis>dp[x][0])
        {
            dp[x][1]=dp[x][0];
            dp[x][0]=dp[v][0]+edge[i].dis;
        }
        else
            if(dp[v][0]+edge[i].dis>dp[x][1])
            {
                dp[x][1]=dp[v][0]+edge[i].dis;
            }
    }
    answer=max((ll)dp[x][0]+dp[x][1],answer);
}
void dfs3(int x,ll uuu)
{
    dis[++ooo]=uuu;
    for(int i=head[x];i;i=edge[i].next)
    {
        if(ooo==2*cnt)return;
        int v=edge[i].to;
        if(v!=q[ooo+1])continue;
        dfs3(v,uuu+edge[i].dis);
    }
}
void find2(int x,int fa,int last)
{
    for(int i=head[x];i;i=edge[i].next)
    {
        if(flag)return;
        int v=edge[i].to;
        if(v==fa && i!=last && i!=(last^1))
        {
            circle[++cnt]=x;
            circle[++cnt]=fa;
            huan[x]=huan[fa]=1;flag=1;
            tmp=max(edge[i].dis,edge[last].dis);
        }
        else if(v!=fa)find2(v,x,i);
    }
}
ll solve(int root)
{
    zongshu=0;
    dfs2(root,0);
    if(zongshu==2)
    {
        answer=0;
        for(int i=head[root];i;i=edge[i].next)answer=max(answer,edge[i].dis);
        return answer;
    }
    for(int i=1;i<=n;i++)stack[i]=0,ins[i]=0;
    flag=top=cnt=answer=0;
    dfs(root,0);
    if(cnt==0)
    {
        flag=0;
        tmp=0;
        find2(root,0,-1);
        for(int i=1;i<=cnt;i++)dpp(circle[i],0),d[circle[i]]=dp[circle[i]][0];
        answer=max(answer,tmp+d[circle[1]]+d[circle[2]]);
        return answer;
    }
    ooo=0;
    for(int i=1;i<=cnt;i++)dpp(circle[i],0),d[circle[i]]=dp[circle[i]][0];
    for(int i=1;i<=cnt;i++)q[i]=circle[i],q[i+cnt]=circle[i],circle[i+cnt]=circle[i];
    dfs3(q[1],0);
    int head=0,tail=1;
    q[++head]=1;
    for(int i=2;i<=2*cnt;i++)
    {
        while(head<=tail && q[head]<=i-cnt)head++;
        answer=max(answer,d[circle[i]]+d[circle[q[head]]]+dis[i]-dis[q[head]]);
        while(head<=tail && d[circle[i]]-dis[i]>=d[circle[q[tail]]]-dis[q[tail]])tail--;q[++tail]=i;
    }
    return answer;
}
signed main()        
{
    freopen("random.out","r",stdin);
    freopen("myanswer.out","w",stdout);
    scanf("%lld",&n);
    int u;ll v;
    for(int i=1;i<=n;i++)scanf("%lld%lld",&u,&v),addedge(i,u,v),addedge(u,i,v);
    for(int i=1;i<=n;i++)if(!vis[i])ans+=solve(i);
    printf("%lld",ans);
    return 0;
}

这应该是这道题最丑最长的一份代码,为了求环跑了一遍dfs,为了标记跑了一遍dfs,为了求前缀和又跑了一遍dfs,特判还有一遍dfs

爱我所爱,行我所行,听从我心,无问西东。