bzoj1791[IOI2008]Island岛屿（基环树+DP）

时间：2024-09-17 11:05:14

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1791 
题目大意：给你一棵n条边的基环树森林，要你求出所有基环树/树的直径之和。n<=1e6

题解：基环树DP写的很少……

树的直径不用解释了，就是NOIP2018D1T3的20分做法，基环树直径，我们可以yy一下然后就能发现答案是2种：1、把环剖去以后其余的子树的直径。2、环上的一部分+选中的2点中各自的最长链。

第一种可以直接dfs求解，对于第二种……我们可以摒弃垃圾的dfs两遍求树的直径的做法，改成DP形式的求树的直径。然后找到一个环时，记录环上的点最深的深度，然后可以把这个环扩展，记录l,r指针，扫描，随便搞一下就能求得答案。

所以本蒟蒻想到的具体做法就是：先topsort一下，把环给找出来，边topsort边DP，然后遇到环再dfs就OK了

不说废话看代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e6+;

int n,cnt,tim,hd[N],v[N],nxt[N],w[N],c[N],du[N],vis[N],q[N];

ll ans,d[N],f[N],a[N],b[N];

void add(int x,int y,int z){v[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt,w[cnt]=z;}

void dfs(int u,int k)

{

    c[u]=k;

    for(int i=hd[u];i;i=nxt[i])if(!c[v[i]])dfs(v[i],k);

}

void topsort()

{

    int qs=,qe=;

    for(int i=;i<=n;i++)if(du[i]==)q[qe++]=i;

    while(qs<qe)

    {

        int u=q[qs++];

        for(int i=hd[u];i;i=nxt[i])

        if(du[v[i]]>)

        {

            du[v[i]]--;

            d[c[u]]=max(d[c[u]],f[u]+f[v[i]]+w[i]);

            f[v[i]]=max(f[v[i]],f[u]+w[i]);

            if(du[v[i]]==)q[qe++]=v[i];

        }

    }

}

void dp(int x,int tp)

{

    int m=,y=x,i;

    do{

        a[++m]=f[y];

        du[y]=;

        for(i=hd[y];i;i=nxt[i])

        if(du[v[i]]>){b[m+]=b[m]+w[i];y=v[i];break;}

    }while(i);

    if(m==)

    {

        int len=;

        for(int i=hd[y];i;i=nxt[i])if(v[i]==x)len=max(len,w[i]);

        d[tp]=max(d[tp],f[x]+f[y]+len);

        return;

    }

    for(int i=hd[y];i;i=nxt[i])if(v[i]==x){b[m+]=b[m]+w[i];break;}

    for(int i=;i<=m;i++)a[m+i]=a[i],b[m+i]=b[m+]+b[i];

    int l=,r=;

    l=r=q[]=;

    for(int i=;i<*m;i++)

    {

        while(l<=r&&i-q[l]>=m)l++;

        d[tp]=max(d[tp],b[i]-b[q[l]]+a[i]+a[q[l]]);

        while(l<=r&&a[q[r]]+b[i]-b[q[r]]<=a[i])r--;

        q[++r]=i;

    }

}

int main()

{

    scanf("%d",&n);

    for(int i=,x,y;i<=n;i++)scanf("%d%d",&x,&y),add(i,x,y),add(x,i,y),du[x]++,du[i]++;

    for(int i=;i<=n;i++)if(!c[i])dfs(i,++tim);

    topsort();

    for(int i=;i<=n;i++)

    if(du[i]>&&!vis[c[i]])vis[c[i]]=,dp(i,c[i]),ans+=d[c[i]];

    printf("%lld",ans);

}

相关文章