BZOJ 3991: [SDOI2015]寻宝游戏 [虚树 树链的并 set]

时间：2023-03-09 00:26:25
BZOJ 3991: [SDOI2015]寻宝游戏 [虚树 树链的并 set]

传送门

题意：

$n$个点的树，$m$次变动使得某个点有宝物或没宝物，询问每次变动后集齐所有宝物并返回原点的最小距离

转化成有根树，求树链的并...

两两树链求并就可以，但我们按照$dfs$序来两两求并，相邻两点深度和减去$lca$的深度

一次只变动一个关键点，用$set$动态维护虚树($dfs$序)就好了

并不需要建树

注意树根不是$1$，但也不能每次减当前树根的深度，所以我们放在最后让树链的并减去树根的深度

【15:02:56】学到一个trick，可以用一个仿函数比较$dfs$序传到$set$里，很方便

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <set>

using namespace std;

typedef long long ll;

const int N=1e5+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,Q,u,v,x;

struct Edge{

    int v,ne,w;

}e[N<<];

int cnt,h[N];

inline void ins(int u,int v,int w){

    cnt++;

    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;

    cnt++;

    e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;

}

int dfn[N],dfc,top[N],size[N],mx[N],deep[N],fa[N];

int pos[N];

ll dis[N];

void dfs(int u){

    size[u]++;

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;

        if(v==fa[u]) continue;

        fa[v]=u;deep[v]=deep[u]+;

        dis[v]=dis[u]+e[i].w;

        dfs(v);

        size[u]+=size[v];

        if(size[v]>size[mx[u]]) mx[u]=v;

    }

}

void dfs2(int u,int anc){

    dfn[u]=++dfc;top[u]=anc;

    pos[dfc]=u;

    if(mx[u]) dfs2(mx[u],anc);

    for(int i=h[u];i;i=e[i].ne)

        if(e[i].v!=fa[u] && e[i].v!=mx[u]) dfs2(e[i].v,e[i].v);

}

inline int lca(int x,int y){

    if(x== || y==) return ;

    while(top[x]!=top[y]){

        if(deep[top[x]]<deep[top[y]]) swap(x,y);

        x=fa[top[x]];

    }

    return deep[x]<deep[y] ? x : y;

}

set<int> S;

set<int>::iterator it;

int has[N],root;

ll chain;

inline void ModifyRoot(){

    it=S.end();

    root=lca(pos[*S.begin()],pos[*(--it)]);

}

void vtrAdd(int x){//printf("Add %d %d\n",x,dfn[x]);

    it=S.insert(dfn[x]).first;

    chain+=dis[x];

    int a=,b=;

    if( it!=S.begin() ) a=pos[*(--it)++];

    if( (++it)!=S.end() ) b=pos[*it];

    //printf("a b %d %d\n",a,b);

    chain+=dis[ lca(a,b) ];

    chain-=dis[ lca(a,x) ] + dis[ lca(b,x) ];

}

void vtrDel(int x){//printf("Del %d %d\n",x,dfn[x]);

    chain-=dis[x];

    it=S.find(dfn[x]);

    int a=,b=;

    if(it!=S.begin()) a=pos[*(--it)++];

    if((++it)!=S.end()) b=pos[*it];

    chain+=dis[ lca(a,x) ] + dis[ lca(b,x) ];

    chain-=dis[ lca(a,b) ];

    S.erase(dfn[x]);

    ModifyRoot();

}

int main(){

    freopen("in","r",stdin);

    n=read();Q=read();

    for(int i=;i<n;i++) u=read(),v=read(),ins(u,v,read());

    dfs();dfs2(,);

    //for(int i=1;i<=n;i++) printf("%d ",dfn[i]);puts("");

    while(Q--){

        x=read(); has[x]^=;

        if(has[x]) vtrAdd(x);

        else vtrDel(x);

        ModifyRoot();

        printf("%lld\n",(chain-dis[root])<<);

    }

}
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <set>

using namespace std;

typedef long long ll;

const int N=1e5+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,Q,u,v,x;

struct Edge{

    int v,ne,w;

}e[N<<];

int cnt,h[N];

inline void ins(int u,int v,int w){

    cnt++;

    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;

    cnt++;

    e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;

}

int dfn[N],dfc,top[N],size[N],mx[N],deep[N],fa[N];

ll dis[N];

void dfs(int u){

    size[u]++;

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;

        if(v==fa[u]) continue;

        fa[v]=u;deep[v]=deep[u]+;

        dis[v]=dis[u]+e[i].w;

        dfs(v);

        size[u]+=size[v];

        if(size[v]>size[mx[u]]) mx[u]=v;

    }

}

void dfs2(int u,int anc){

    dfn[u]=++dfc;top[u]=anc;

    if(mx[u]) dfs2(mx[u],anc);

    for(int i=h[u];i;i=e[i].ne)

        if(e[i].v!=fa[u] && e[i].v!=mx[u]) dfs2(e[i].v,e[i].v);

}

inline int lca(int x,int y){

    if(x== || y==) return ;

    while(top[x]!=top[y]){

        if(deep[top[x]]<deep[top[y]]) swap(x,y);

        x=fa[top[x]];

    }

    return deep[x]<deep[y] ? x : y;

}

struct DFSN{

    bool operator ()(int x,int y){return dfn[x]<dfn[y];}

};

set<int,DFSN> S;

set<int,DFSN>::iterator it;

int has[N],root;

ll chain;

inline void ModifyRoot(){

    it=S.end();

    root=lca(*S.begin(),*(--it));

}

void vtrAdd(int x){//printf("Add %d %d\n",x,dfn[x]);

    it=S.insert(x).first;

    chain+=dis[x];

    int a=,b=;

    if( it!=S.begin() ) a=*(--it)++;

    if( (++it)!=S.end() ) b=*it;

    //printf("a b %d %d\n",a,b);

    chain+=dis[ lca(a,b) ];

    chain-=dis[ lca(a,x) ] + dis[ lca(b,x) ];

}

void vtrDel(int x){//printf("Del %d %d\n",x,dfn[x]);

    chain-=dis[x];

    it=S.find(x);

    int a=,b=;

    if(it!=S.begin()) a=*(--it)++;

    if((++it)!=S.end()) b=*it;

    chain+=dis[ lca(a,x) ] + dis[ lca(b,x) ];

    chain-=dis[ lca(a,b) ];

    S.erase(x);

    ModifyRoot();

}

int main(){

    freopen("in","r",stdin);

    n=read();Q=read();

    for(int i=;i<n;i++) u=read(),v=read(),ins(u,v,read());

    dfs();dfs2(,);

    //for(int i=1;i<=n;i++) printf("%d ",dfn[i]);puts("");

    while(Q--){

        x=read(); has[x]^=;

        if(has[x]) vtrAdd(x);

        else vtrDel(x);

        ModifyRoot();

        printf("%lld\n",(chain-dis[root])<<);

    }

}