【BZOJ】3991: [SDOI2015]寻宝游戏虚树+DFS序+set

淩亂°似流年 2022-01-12 01:07 156阅读 0赞

【题意】给定n个点的带边权树，对于树上存在的若干特殊点，要求任选一个点开始将所有特殊点走遍后返回。现在初始没有特殊点，m次操作每次增加或减少一个特殊点，求每次操作后的总代价。n,m<=10^5。

【算法】虚树+DFS序+set

【题解】每次询问相当于求**两倍虚树路径和**。

模拟虚树上dfs序的转移会发现，**dfs序相邻（1和n视为相邻）的两点路径值的总和，就是虚树路径和的两倍**。

那么只需要用set维护特殊点集合，每次根据前驱后继更改答案。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<set>
    #define ll long long
    using namespace std;
    const int maxn=100010;
    int n,m,first[maxn],tot,deep[maxn],in[maxn],dfsnum=0,f[maxn][30];
    ll dis[maxn];
    bool v[maxn];
    struct cmp{
        bool operator ()(int x,int y){
         return in[x]<in[y];}
    };
    set<int,cmp>s;
    set<int,cmp>::iterator it;
    struct edge{
         int v,w,from;}e[maxn*2];
    void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}
    void dfs(int x,int fa){
        in[x]=++dfsnum;
        for(int j=1;(1<<j)<=deep[x];j++)f[x][j]=f[f[x][j-1]][j-1];
        for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){
            deep[e[i].v]=deep[x]+1;
            dis[e[i].v]=dis[x]+e[i].w;
            f[e[i].v][0]=x;
            dfs(e[i].v,x);
        }
    }
    int lca(int x,int y){
        if(deep[x]<deep[y])swap(x,y);
        int d=deep[x]-deep[y];
        for(int i=0;i<=20;i++)if((1<<i)&d)x=f[x][i];
        if(x==y)return x;
        for(int i=20;i>=0;i--)if((1<<i)<=deep[x]&&f[x][i]!=f[y][i]){
            x=f[x][i];y=f[y][i];
        }
        return f[x][0];
    }
    ll  p(int x,int y){
         return dis[x]+dis[y]-2*dis[lca(x,y)];}
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            insert(u,v,w);insert(v,u,w);
        }
        dfs(1,-1);
        ll sum=0;
        while(m--){
            int x,a,b;
            scanf("%d",&x);
            if(!v[x]){
                if(s.empty())s.insert(x),v[x]=1;
                it=s.lower_bound(x);
                if(it!=s.end())b=*it;else b=*s.begin();
                if(it!=s.begin())a=*(--it);else it=s.end(),a=*(--it);
                sum+=p(a,x)+p(x,b)-p(a,b);
                s.insert(x);v[x]=1;
            }
            else{
                it=s.find(x);
                if((++it)!=s.end())b=*it;else b=*s.begin();
                it--;
                if(it!=s.begin())a=*(--it);else it=s.end(),a=*(--it);
                if(s.size()>1)sum+=p(a,b)-p(a,x)-p(b,x);
                s.erase(x);v[x]=0;
            }
            printf("%lld\n",sum);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/onioncyc/p/8470844.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/8d9faf98c831484185abb03db1c6a6c1.png