[BZOJ3611/Luogu4103][HEOI2014]大工程(虚树,树型动态规划)

发布于 2018-05-25  76 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3611/Luogu4103][HEOI2014]大工程(虚树,树型动态规划)

Description

国家有一个大工程,要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊,可以看成是一个单位边权的树,城市位于顶点上。
在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
现在国家有很多个计划,每个计划都是这样,我们选中了 k 个点,然后在它们两两之间 新建 C(k,2)条 新通道。
现在对于每个计划,我们想知道:
1.这些新通道的代价和
2.这些新通道中代价最小的是多少
3.这些新通道中代价最大的是多少

Tag

虚树,树型动态规划

解决思路

建立出虚树后,现在要求的就是各个关键点之间的路径长度之和,两端均为关键点的最长和最短路径,在虚树上动态规划求解。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1001000*2;
const int maxM=maxN*2;
const int maxBit=20;
const int inf=2000000000;
const ll INF=1e18;

int n,K;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
int dfncnt=0,Dfn[maxN],Last[maxN],Fa[maxBit][maxN];
ll Depth[maxN];
int Node[maxN<<1],Stack[maxN];

void Add_Edge(int u,int v);
void dfs_init(int u,int fa);
bool cmp(int a,int b);
int GetLCA(int u,int v);
int Dist(int u,int v);

namespace Tree
{
    int nodecnt,Mark[maxN];
    int edgecnt,Head[maxN],Next[maxM],V[maxM];
    ll Size[maxN],F[maxN],E[maxN];
    ll Ans1,Ans2,Ans3;

    void Add_Edge(int u,int v);
    void Do();
    void dfs(int u,int fa);
}

int main()
{
    mem(Head,-1);
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        Add_Edge(u,v);
    }

    dfs_init(1,0);
    for (int i=1;i<maxBit;i++)
        for (int j=1;j<=n;j++)
            if ((Fa[i-1][j])&&(Fa[i-1][Fa[i-1][j]]))
                Fa[i][j]=Fa[i-1][Fa[i-1][j]];

    int TQ;scanf("%d",&TQ);
    while (TQ--)
    {
        scanf("%d",&K);
        for (int i=1;i<=K;i++) scanf("%d",&Node[i]);
        Tree::nodecnt=K;
        for (int i=1;i<=K;i++) Tree::Mark[Node[i]]=1;

        sort(&Node[1],&Node[K+1],cmp);
        for (int i=1;i<K;i++) Node[i+K]=GetLCA(Node[i],Node[i+1]);
        K=K+K-1;Node[++K]=1;
        sort(&Node[1],&Node[K+1],cmp);K=unique(&Node[1],&Node[K+1])-Node-1;

        Tree::edgecnt=0;
        for (int i=1;i<=K;i++) Tree::Head[Node[i]]=-1;

        int top=0;
        for (int i=1;i<=K;i++)
        {
            while ((top)&&(Last[Stack[top]]<Dfn[Node[i]])) top--;
            if (top) Tree::Add_Edge(Stack[top],Node[i]);
            Stack[++top]=Node[i];
        }
        Tree::Do();

        printf("%lld %lld %lld\n",Tree::Ans1,Tree::Ans2,Tree::Ans3);
        for (int i=1;i<=K;i++) Tree::Mark[Node[i]]=0;
    }
    return 0;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;V[edgecnt]=u;
    return;
}

void dfs_init(int u,int fa)
{
    Dfn[u]=++dfncnt;Depth[u]=Depth[fa]+1;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=fa)
        {
            Fa[0][V[i]]=u;
            dfs_init(V[i],u);
        }
    Last[u]=dfncnt;return;
}

bool cmp(int a,int b){
    return Dfn[a]<Dfn[b];
}

int GetLCA(int u,int v)
{
    if (Depth[u]<Depth[v]) swap(u,v);
    for (int i=maxBit-1;i>=0;i--) if ((Fa[i][u])&&(Depth[Fa[i][u]]>=Depth[v])) u=Fa[i][u];
    if (u==v) return u;
    for (int i=maxBit-1;i>=0;i--) if ((Fa[i][u])&&(Fa[i][v])&&(Fa[i][u]!=Fa[i][v])) u=Fa[i][u],v=Fa[i][v];
    return Fa[0][u];
}

int Dist(int u,int v)
{
    int lca=GetLCA(u,v);
    return Depth[u]+Depth[v]-2*Depth[lca];
}

namespace Tree
{
    void Add_Edge(int u,int v)
    {
        edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
        edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;V[edgecnt]=u;
        return;
    }

    void Do()
    {
        Ans1=0;Ans2=INF;Ans3=-INF;
        dfs(1,0);
    }

    void dfs(int u,int fa)
    {
        F[u]=(Mark[u])?(0):(-INF);
        E[u]=(Mark[u])?(0):(INF);
        Size[u]=Mark[u];
        for (int i=Head[u];i!=-1;i=Next[i])
            if (V[i]!=fa)
            {
                dfs(V[i],u);Size[u]+=Size[V[i]];
                int w=Dist(V[i],u);
                Ans1=Ans1+1ll*Size[V[i]]*(nodecnt-Size[V[i]])*w;
                Ans2=min(Ans2,E[u]+E[V[i]]+w);
                Ans3=max(Ans3,F[u]+F[V[i]]+w);
                E[u]=min(E[u],E[V[i]]+w);
                F[u]=max(F[u],F[V[i]]+w);
            }
        return;
    }
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3611/Luogu4103][HEOI2014]大工程(虚树,树型动态规划)


HNCJ OIer 一枚