[BZOJ3991/Luogu3320][SDOI2015]寻宝游戏(dfs序)

发布于 26 天前  55 次阅读


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

本文链接地址:[BZOJ3991/Luogu3320][SDOI2015]寻宝游戏(dfs序)

Description

小B最近正在玩一个寻宝游戏,这个游戏的地图中有N个村庄和N-1条道路,并且任何两个村庄之间有且仅有一条路径可达。游戏开始时,玩家可以任意选择一个村庄,瞬间转移到这个村庄,然后可以任意在地图的道路上行走,若走到某个村庄中有宝物,则视为找到该村庄内的宝物,直到找到所有宝物并返回到最初转移到的村庄为止。小B希望评测一下这个游戏的难度,因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这个游戏中宝物经常变化,有时某个村庄中会突然出现宝物,有时某个村庄内的宝物会突然消失,因此小B需要不断地更新数据,但是小B太懒了,不愿意自己计算,因此他向你求助。为了简化问题,我们认为最开始时所有村庄内均没有宝物

Tag

dfs序

解决思路

题目中并没有限制询问点数之和,所以不能用虚树做呢。
但是,询问有一个良好的性质,即每一次最多只会动一个点。考虑询问的内容,我们发现,只要从任意一个关键点出发,每次均走到没有经过$dfn$序最近的的一个关键点,最后再返回来即可。
所以用$set$以$dfn$序维护一个点的集合,每一次加入或删除的时候讨论一下,维护答案。
注意当集合中元素个数小于等于$2$个和插入元素为头或尾的时候的特殊处理。

代码

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

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

const int maxN=101000;
const int maxM=maxN*2;
const int maxBit=18;
const int inf=2147483647;

class SetData
{
public:
    int pos;
};

int n,m;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
ll W[maxM];
int dfncnt,Dfn[maxN];
int Depth[maxN],Fa[maxBit][maxN];
ll Dist[maxN];
set<SetData> Set;
int Mark[maxN];

bool operator < (SetData A,SetData B);
void Add_Edge(int u,int v,int w);
void dfs_init(int u,int fa);
int GetLCA(int u,int v);
ll GetDist(int u,int v);

int main()
{
    mem(Head,-1);
    scanf("%d%d",&n,&m);
    for (int i=1;i<n;i++)
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        Add_Edge(u,v,w);
    }
    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]];

    ll Ans=0;
    for (int i=1;i<=m;i++)
    {
        int u;scanf("%d",&u);
        SetData uu=((SetData){u});
        if (Mark[u])
        {
            Mark[u]=0;
            if (Set.size()==1){
                Set.erase(uu);Ans=0;
            }
            else if (Set.size()==2){
                Set.erase(uu);Ans=0;
            }
            else
            {
                set<SetData>::iterator p1=Set.find(uu),p2,p3;
                if ((*p1).pos==(*Set.begin()).pos)
                {
                    p2=p1;p2++;
                    Ans-=GetDist((*p1).pos,(*p2).pos);
                    Ans-=GetDist((*p1).pos,(*Set.rbegin()).pos);
                    Set.erase(p1);
                    Ans+=GetDist((*Set.begin()).pos,(*Set.rbegin()).pos);
                }
                else if ((*p1).pos==(*Set.rbegin()).pos)
                {
                    p2=p1;p2--;
                    Ans-=GetDist((*p1).pos,(*p2).pos);
                    Ans-=GetDist((*p1).pos,(*Set.begin()).pos);
                    Set.erase(p1);
                    Ans+=GetDist((*Set.begin()).pos,(*Set.rbegin()).pos);
                }
                else
                {
                    p2=p1;p2--;p3=p1;p3++;
                    Ans-=GetDist((*p1).pos,(*p2).pos);
                    Ans-=GetDist((*p1).pos,(*p3).pos);
                    Ans+=GetDist((*p2).pos,(*p3).pos);
                    Set.erase(p1);
                }
            }
        }
        else
        {
            Mark[u]=1;
            Set.insert(uu);
            set<SetData>::iterator p1=Set.find(uu),p2,p3;
            if (Set.size()==1) Ans=0;
            else if (Set.size()==2) Ans=GetDist((*Set.begin()).pos,(*Set.rbegin()).pos)*2ll;
            else
            {
                if ((*p1).pos==(*Set.begin()).pos)
                {
                    p2=p1;p2++;
                    Ans-=GetDist((*p2).pos,(*Set.rbegin()).pos);
                    Ans+=GetDist((*p1).pos,(*p2).pos);
                    Ans+=GetDist((*p1).pos,(*Set.rbegin()).pos);
                }
                else if ((*p1).pos==(*Set.rbegin()).pos)
                {
                    p2=p1;p2--;
                    Ans-=GetDist((*p2).pos,(*Set.begin()).pos);
                    Ans+=GetDist((*p1).pos,(*p2).pos);
                    Ans+=GetDist((*p1).pos,(*Set.begin()).pos);
                }
                else
                {
                    p2=p1;p2--;p3=p1;p3++;
                    Ans-=GetDist((*p2).pos,(*p3).pos);
                    Ans+=GetDist((*p1).pos,(*p2).pos);
                    Ans+=GetDist((*p1).pos,(*p3).pos);
                }
            }
        }
        printf("%lld\n",Ans);
    }
    return 0;
}

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

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

bool operator < (SetData A,SetData B){
    return Dfn[A.pos]<Dfn[B.pos];
}

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];
}

ll GetDist(int u,int v)
{
    int lca=GetLCA(u,v);
    return Dist[u]-Dist[lca]+Dist[v]-Dist[lca];
}

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

本文链接地址:[BZOJ3991/Luogu3320][SDOI2015]寻宝游戏(dfs序)


HNCJ OIer 一枚