[SDOI2015]寻宝游戏

第一行，两个整数N、M，其中M为宝物的变动次数。
接下来的N-1行，每行三个整数x、y、z，表示村庄x、y之间有一条长度为z的道路。
接下来的M行，每行一个整数t，表示一个宝物变动的操作。
若该操作前村庄t内没有宝物，则操作后村庄内有宝物；若该操作前村庄t内有宝物，则操作后村庄内没有宝物。

M行，每行一个整数，其中第i行的整数表示第i次操作之后玩家找到所有宝物需要行走的最短路程。若只有一个村庄内有宝物，或者所有村庄内都没有宝物，则输出0。

C++ 解法, 执行用时: 229ms, 内存消耗: 20012K, 提交时间: 2021-09-15 21:42:26

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N=1e5+5;
typedef long long ll;
struct edge{
	int v;
	int nxt;
	ll w;
}e[N<<1];
int cnt=0,head[N],dep[N],dfn[N],df=0,vis[N],f[N][20];
ll len[N];
void addedge(int u,int v,ll w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
} 
/*
维护一个深度数组 一个点到根节点距离的数组 
*/
void dfs(int u,int fa){
	dfn[u]=++df;
	f[u][0]=fa;
	for(int i=1;i<=19;i++){
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(int i=head[u];~i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa)continue;
		len[v]=len[u]+e[i].w;
		dep[v]=dep[u]+1;
		dfs(v,u);
	}
}
set<pii> s;
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=19;i>=0;i--){
		if(dep[f[x][i]]<dep[y])continue;
		else x=f[x][i];
	}
	if(x==y)return x;
	for(int i=19;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];y=f[y][i];
		}
	}
	return f[x][0];
}
ll dis(int x,int y){
	return len[x]+len[y]-2*len[lca(x,y)];
}
int getl(int x){
	auto it=s.find(mp(dfn[x],x));
	if(it==s.begin())it=s.end();
	--it;
	return (*it).se;
}
int getr(int x){
	auto it=s.find(mp(dfn[x],x));
	if(++it==s.end())it=s.begin();
	return (*it).se;
}
int main(){
	int n,m;
	cin>>n>>m;
	memset(head,-1,sizeof head);
	for(int i=1;i<n;i++){
		int x,y;
		ll z;
		scanf("%d%d%lld",&x,&y,&z);
		addedge(x,y,z);
		addedge(y,x,z);
	}
	dfs(1,1);
	ll ans=0;
	for(int i=1;i<=m;i++){
		int x;
		scanf("%d",&x);
		if(!vis[x]){
			s.insert(mp(dfn[x],x));
			int l=getl(x),r=getr(x);
			ans+=dis(l,x)+dis(x,r)-dis(l,r);
		}
		else {
			int l=getl(x),r=getr(x);
			ans+=dis(l,r)-dis(x,r)-dis(l,x);
			s.erase(mp(dfn[x],x));
		}
		vis[x]^=1;
		printf("%lld\n",ans);
	}
	return 0;
}

详情