「SDOI2015」寻宝游戏 - 虚树+欧拉环游序

题目大意

    小B最近正在玩一个寻宝游戏，这个游戏的地图中有$N$个村庄和$N-1$条道路，并且任何两个村庄之间有且仅有一条路径可达。游戏开始时，玩家可以任意选择一个村庄，瞬间转移到这个村庄，然后可以任意在地图的道路上行走，若走到某个村庄中有宝物，则视为找到该村庄内的宝物，直到找到所有宝物并返回到最初转移到的村庄为止。小B希望评测一下这个游戏的难度，因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这个游戏中宝物经常变化，有时某个村庄中会突然出现宝物，有时某个村庄内的宝物会突然消失，因此小B需要不断地更新数据，但是小B太懒了，不愿意自己计算，因此他向你求助。为了简化问题，我们认为最开始时所有村庄内均没有宝物。

---

题目分析

对关键点建棵虚树，显然，按照欧拉环游序走是代价最小的。
因此用set维护这棵虚树的欧拉环游序，加入/删除点的时候查询一下前驱后继添加影响。
最后加上第一个点到最后一个点的路径长度即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=100005;

struct Edge {
	int from,to;
	LL dist;
};

int n,m,Depth[maxn],father[maxn],Size[maxn],Son[maxn],Dfn[maxn],M[maxn],Top[maxn],step=0;
LL Dist[maxn],ans=0;
bool a[maxn];
vector<Edge> edges[maxn];

void AddEdge(int x,int y,LL v) {
	edges[x].push_back((Edge) {x,y,v});
}

void Dfs(int Now,int fa,int depth,LL dist) {
	Depth[Now]=depth;
	Dist[Now]=dist;
	father[Now]=fa;
	Size[Now]=1;
	for(Edge& e:edges[Now]) {
		int Next=e.to;
		if(Next==fa)continue;
		Dfs(Next,Now,depth+1,dist+e.dist);
		Size[Now]+=Size[Next];
		if(Size[Next]>Size[Son[Now]])Son[Now]=Next;
	}
}

void Dfs2(int Now,int top) {
	Top[Now]=top;
	Dfn[Now]=++step;
	M[step]=Now;
	if(Son[Now])Dfs2(Son[Now],top);
	for(Edge& e:edges[Now]) {
		int Next=e.to;
		if(Next==father[Now]||Next==Son[Now])continue;
		Dfs2(Next,Next);
	}
}

int LCA(int x,int y) {
	for(; Top[x]!=Top[y]; x=father[Top[x]])if(Depth[Top[x]]<Depth[Top[y]])swap(x,y);
	return Depth[x]<Depth[y]?x:y;
}

LL dist(int x,int y) {
	return Dist[x]+Dist[y]-(Dist[LCA(x,y)]<<1);
}

set<int> S;

void modify(int x,int delta) {
	auto it=(delta==-1)?S.find(Dfn[x]):S.insert(Dfn[x]).first,it2=it;
	int pre=0,suc=0;
	if(it!=S.begin())pre=M[*--it];
	if(++it2!=S.end())suc=M[*it2];
	if(pre)ans+=dist(pre,x)*delta;
	if(suc)ans+=dist(x,suc)*delta;
	if(pre&&suc)ans+=dist(pre,suc)*delta*-1;
	if(delta==-1)S.erase(Dfn[x]);
}

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<n; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		AddEdge(x,y,v);
		AddEdge(y,x,v);
	}
	Dfs(1,-1,1,0);
	Dfs2(1,1);
	for(int i=1; i<=m; i++) {
		int x=Get_Int();
		if(a[x])modify(x,-1);
		else modify(x,1);
		a[x]^=1;
		if(S.empty())puts("0");
		else printf("%lld\n",ans+dist(M[*S.begin()],M[*--S.end()]));
	}
	return 0;
}