树形dp 基环树直径 bzoj1791 ioi2008island

这个题真的好麻烦啊。。。

就是给一堆基环树然后求出他们的直径的和

我们首先不考虑环，然后对于每个点求出他所能走到的最大深度，

然后缩点，就成了一个面包圈一样的环了

然后脱环成链直接用单调队列dp就可以了

队列中维护dp的决策，由于决策是有单调性的。。。

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<algorithm>
#define MAX 1000010
#define ll long long
#define max(a,b) a>b?a:b
#define rep(i,j,k) for(int i=j;i<=k;i++)
 
using namespace std;
 
int next[MAX*2],head[MAX],to[2*MAX],n,tot=0;
int scc_num=0,value[MAX*2];
int du[MAX]={0};ll d[MAX];
int vis[MAX]={0};
int q[MAX*2];
ll ans=0,f[MAX],a[MAX*2],b[2*MAX];
int done[MAX],scc[MAX]={0};
 
void add(int from,int To,int weight)
{
    du[To]++;
    tot++;
    to[tot]=To;
    next[tot]=head[from];
    value[tot]=weight;
    head[from]=tot;
    return;
}
 
void bfs(int x,int number)
{
    queue<int>q;
    q.push(x);
    scc[x]=number;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];i!=-1;i=next[i])
            if(!scc[to[i]])
                scc[to[i]]=number,q.push(to[i]);
    }
    return;
}

void topsort()
{
    queue<int>q;
    rep(i,1,n)
        if(du[i]==1)
            q.push(i);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];i!=-1;i=next[i])
            if(du[to[i]]>1)
            {
                d[scc[now]]=max(d[scc[now]],f[now]+f[to[i]]+value[i]);
                f[to[i]]=max(f[to[i]],f[now]+value[i]);
                if((--du[to[i]])==1)
                    q.push(to[i]);
            }
    }
    return;
}

void dp(int sc,int x)
{
    int y=x,p,t=0,l=0,r;
    do
    {
        a[++t]=f[y];
        du[y]=1;
        for(p=head[y];p!=-1;p=next[p])
            if(du[to[p]]>1)
            {
                y=to[p];
                b[t+1]=b[t]+value[p];
                break;
            }
    }while(p!=-1);
 
    if(t==2)
    {
        for(int i=head[y];i!=-1;i=next[i])
            if(to[i]==x)
                l=max(l,value[i]);
        d[sc]=max(d[sc],f[x]+f[y]+l);
        return;
    }
 
    for(int i=head[y];i!=-1;i=next[i])
        if(to[i]==x)
        {
            b[t+1]=b[t]+value[i];
            break;
        }
    rep(i,1,t-1)
        a[t+i]=a[i],b[t+i]=b[t+1]+b[i];
    r=1;
    q[l=1]=1;
    for(int i=2;i<2*t;i++)
    {
        while(l<=r&&i-q[l]>=t)
            l++;
        d[sc]=max(d[sc],a[i]+a[q[l]]+b[i]-b[q[l]]);
        while(l<=r&&a[q[r]]+b[i]-b[q[r]]<=a[i])
            r--;
        q[++r]=i;
    }
    return;
}
 
int main()
{
    memset(next,-1,sizeof(next));
    scanf("%d",&n);
    for(int i=1,a1,a2;i<=n;i++)
        scanf("%d%d",&a1,&a2),add(i,a1,a2),add(a1,i,a2);
    scc_num=0;
    rep(i,1,n)
        if(!scc[i])
            bfs(i,++scc_num);
    topsort();
    rep(i,1,n)
        if(du[i]>1&&!vis[scc[i]])
        {
            vis[scc[i]]=1;
            dp(scc[i],i);
            ans+=d[scc[i]];
        }
	cout<<ans<<endl;
    return 0;
}

树形dp 基环树直径 bzoj1791 ioi2008island,布布扣,bubuko.com

树形dp 基环树直径 bzoj1791 ioi2008island

原文：http://blog.csdn.net/wbysr/article/details/22321511