[BZOJ3572/Luogu3233][HNOI2014]世界树(虚树,树型动态规划)

发布于 2018-05-27  191 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3572/Luogu3233][HNOI2014]世界树(虚树,树型动态规划)

Description

世界树是一棵无比巨大的树,它伸出的枝干构成了整个世界。在这里,生存着各种各样的种族和生灵,他们共同信奉着绝对公正公平的女神艾莉森,在他们的信条里,公平是使世界树能够生生不息、持续运转的根本基石。
世界树的形态可以用一个数学模型来描述:世界树中有n个种族,种族的编号分别从1到n,分别生活在编号为1到n的聚居地上,种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连,道路的长度为1。保证连接的方式会形成一棵树结构,即所有的聚居地之间可以互相到达,并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度;例如,若聚居地a和b之间有道路,b和c之间有道路,因为每条道路长度为1而且又不可能出现环,所卧a与c之间的距离为2。
出于对公平的考虑,第i年,世界树的国王需要授权m[i]个种族的聚居地为临时议事处。对于某个种族x(x为种族的编号),如果距离该种族最近的临时议事处为y(y为议事处所在聚居地的编号),则种族x将接受y议事处的管辖(如果有多个临时议事处到该聚居地的距离一样,则y为其中编号最小的临时议事处)。
现在国王想知道,在q年的时间里,每一年完成授权后,当年每个临时议事处将会管理多少个种族(议事处所在的聚居地也将接受该议事处管理)。 现在这个任务交给了以智慧著称的灵长类的你:程序猿。请帮国王完成这个任务吧。

Tag

虚树,树型动态规划

解决思路

首先对于每一个询问建立出虚树。对于在虚树中的点,我们可以比较方便地求出距离每一个点最近的议事处的位置。那么对于不在虚树中的点,它一定能连接到虚树上的点或虚树上的边。
对于虚树上的每一对边,如果边两边的点被管辖的点相同,那么这整个一条边上的点都是如此。反之,我们可以倍增地找到一个中间点,使得这个点以下的部分与下端点同,以上的部分与上端点同。
当然,由于建立出虚树后有一些点已经在虚树中统计过了,所以另外还要考虑去重的问题。可以用一个$sum$数组来统计,表示虚树上的贡献,开始的时候置为$size$,然后每计算一部分就从中减掉,最后再把虚树上的贡献统计到答案中。

代码

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

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

const int maxN=301000;
const int maxM=maxN*2;
const int maxBit=16;
const int inf=2147483647;

int n,m;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
int dfncnt,Dfn[maxN],Last[maxN],Depth[maxN],Fa[maxBit][maxN],Size[maxN];
int Stack[maxN],Node[maxN<<1],Mark[maxN],Input[maxN],Sum[maxN],Cnt[maxN],nowFa[maxN];
int Near[maxN];

void Add_Edge(int u,int v);
void dfs_init(int u,int fa);
int GetLCA(int u,int v);
int GetDist(int u,int v);
bool cmp(int u,int v);
void dfs1(int u,int fa);
void dfs2(int u,int fa);
void Do(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]];

    edgecnt=0;
    mem(Head,-1);
    int TTT;scanf("%d",&TTT);
    while (TTT--)
    {
        int K,KK;scanf("%d",&K);KK=K;
        for (int i=1;i<=K;i++) scanf("%d",&Node[i]),Input[i]=Node[i];

        for (int i=1;i<=K;i++) Mark[Node[i]]=1,Cnt[Node[i]]=0,Near[Node[i]]=Node[i];

        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;Node[K]=1;
        sort(&Node[1],&Node[K+1],cmp);K=unique(&Node[1],&Node[K+1])-Node-1;

        edgecnt=0;
        for (int i=1;i<=K;i++) 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) Add_Edge(Stack[top],Node[i]);
            Stack[++top]=Node[i];
        }

        dfs1(1,0);
        dfs2(1,0);

        for (int i=1;i<=K;i++)
            for (int j=Head[Node[i]];j!=-1;j=Next[j])
                if (V[j]!=nowFa[Node[i]])
                    Do(V[j],Node[i]);

        for (int i=1;i<=K;i++) Cnt[Near[Node[i]]]+=Sum[Node[i]];

        for (int i=1;i<=KK;i++) printf("%d ",Cnt[Input[i]]);
        printf("\n");

        for (int i=1;i<=K;i++) Mark[Node[i]]=Cnt[Node[i]]=Sum[Node[i]]=Near[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)
{
    Depth[u]=Depth[fa]+1;Dfn[u]=++dfncnt;Size[u]=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);
            Size[u]+=Size[V[i]];
        }
    Last[u]=dfncnt;
    return;
}

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 GetDist(int u,int v){
    return Depth[u]+Depth[v]-2*Depth[GetLCA(u,v)];
}

bool cmp(int u,int v){
    return Dfn[u]<Dfn[v];
}

void dfs1(int u,int fa)
{
    Sum[u]=Size[u];
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=fa)
        {
            nowFa[V[i]]=u;
            dfs1(V[i],u);
            if (Near[V[i]]==0) continue;
            int d1=GetDist(Near[V[i]],u),d2=GetDist(Near[u],u);
            if ((Near[u]==0)||(d1<d2)||((d1==d2)&&(Near[V[i]]<Near[u])))
                Near[u]=Near[V[i]];
        }
    return;
}

void dfs2(int u,int fa)
{
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=fa)
        {
            int d1=GetDist(Near[u],V[i]),d2=GetDist(Near[V[i]],V[i]);
            if ((Near[V[i]]==0)||(d1<d2)||((d1==d2)&&(Near[u]<Near[V[i]]))) Near[V[i]]=Near[u];
            dfs2(V[i],u);
        }
    return;
}

void Do(int u,int fa)
{
    int An=u;
    for (int i=maxBit;i>=0;i--) if ((Fa[i][An])&&(Depth[Fa[i][An]]>Depth[fa])) An=Fa[i][An];
    Sum[fa]-=Size[An];
    if (Near[u]==Near[fa])
    {
        Cnt[Near[u]]+=Size[An]-Size[u];
        return;
    }
    int now=u;
    for (int i=maxBit-1;i>=0;i--)
        if ((Fa[i][now])&&(Depth[Fa[i][now]]>Depth[fa]))
        {
            int d1=GetDist(Near[u],Fa[i][now]),d2=GetDist(Near[fa],Fa[i][now]);
            if ((d1<d2)||((d1==d2)&&(Near[u]<Near[fa]))) now=Fa[i][now];
        }
    Cnt[Near[u]]+=Size[now]-Size[u];
    Cnt[Near[fa]]+=Size[An]-Size[now];
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3572/Luogu3233][HNOI2014]世界树(虚树,树型动态规划)


HNCJ OIer