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

传送门

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

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

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

代码如下：

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