「SDOI2015」寻宝游戏 - 虚树+欧拉环游序 | Bill Yang's Blog

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

题目大意

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


题目分析

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


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#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;
}
姥爷们赏瓶冰阔落吧~
0%