set+LCA--luoguP3320 [SDOI2015]寻宝游戏

本文主要是介绍set+LCA--luoguP3320 [SDOI2015]寻宝游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

说是虚树…其实也没真正用到虚树

因为他最后要走回去，所以每条边都会经过两遍，选哪个点都无所谓，所以可以按照 $d f s$ 序排序，加入一个新点的时候就把前驱后继的距离减掉再加上它到前驱和它到后继的距离，这个求一下 $l c a$ 就行，删掉点就是反过来。

一开始 $s e t$ 写的不太好 $r e$ 了，注意判一下它没有前驱或者后继的情况

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#define N 100005
#define LL long long
using namespace std;template<class T>inline void rd(T &x){x=0; short f=1; char c=getchar();while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();x*=f;
}int n,m,cnt,head[N],nxt[N<<1],to[N<<1],w[N<<1];
int dep[N],f[N][20],dfn[N],num,tp[N];
LL dis[N],ans;inline void add(int x,int y,int z){to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt,w[cnt]=z;to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt,w[cnt]=z;
}void dfs(int u,int fa){dfn[u]=++num;for(int i=head[u],v;i;i=nxt[i])if((v=to[i])!=fa){dep[v]=dep[u]+1; f[v][0]=u; dis[v]=dis[u]+w[i];for(int j=1;j<=17;j++)f[v][j]=f[f[v][j-1]][j-1];dfs(v,u);}
}inline int LCA(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int i=17;i>=0;i--)if(dep[f[x][i]]>=dep[y]) x=f[x][i];if(x==y) return x;for(int i=17;i>=0;i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];
}struct qwq{int id,k;qwq(const int xx=0,const int yy=0){id=xx,k=yy;}inline bool operator <(const qwq &x) const{return k<x.k||(k==x.k&&id<x.id);}
};
set<qwq> st;
set<qwq>::iterator it,it1,it2;inline void solve(int x){it=st.find(qwq(x,dfn[x]));if(it==st.begin()) it1=st.end(),it1--;else it1=it,it1--;it2=it; it2++;if(it2==st.end()) it2=st.begin();
}inline LL calc1(){return dis[it1->id]+dis[it2->id]-dis[LCA(it1->id,it2->id)]*2;
}inline LL calc2(){return dis[it->id]*2+dis[it1->id]+dis[it2->id]-dis[LCA(it->id,it1->id)]*2-dis[LCA(it->id,it2->id)]*2;
}int main(){rd(n); rd(m); int x,y,z;for(int i=1;i<n;i++){rd(x),rd(y),rd(z);add(x,y,z);}dfs(1,0);while(m--){rd(x);if(!tp[x]){st.insert(qwq(x,dfn[x])); solve(x);ans-=calc1(),ans+=calc2();}else{solve(x);ans+=calc1(),ans-=calc2();st.erase(qwq(x,dfn[x]));}printf("%lld\n",ans); tp[x]^=1;}return 0;
}