题目
传送门：loj10132
在 Adera 的异时空中有一张地图。这张地图上有 N 个点，有N-1 条双向边把它们连通起来。起初地图上没有任何异象石，在接下来的 M 个时刻中，每个时刻会发生以下三种类型的事件之一：
- 地图的某个点上出现了异象石（已经出现的不会再次出现）；
- 地图某个点上的异象石被摧毁（不会摧毁没有异象石的点）；
- 向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。
请你作为玩家回答这些问题。下图是一个例子，灰色节点表示出现了异象石，加粗的边表示被选为连通异象石的边集。
输入格式
第一行有一个整数 N，表示点的个数；
接下来 N-1 行每行三个整数 x,y,z，表示点 x 和 y 之间有一条长度为 z 的双向边；
第 N+1 行有一个正整数 M；
接下来 M 行每行是一个事件，事件是以下三种格式之一：
-
+ x：表示点 x 上出现了异象石； -
- x：表示点 x 上的异象石被摧毁； -
?：表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。
输出格式
对于每个 ? 事件，输出一个整数表示答案。
样例
样例输入
6
1 2 1
1 3 5
4 1 7
4 5 3
6 4 2
10
+ 3
+ 1
?
+ 6
?
+ 5
?
- 6
- 3
?
样例输出
5
14
17
10
数据范围与提示
对于100%的数据，1 ≤ n, m ≤ 105, 1 ≤ x, y ≤ n, x ≠ y, 1 ≤ z ≤ 109。
分析
发现按dfs序排有异象石的点，算出相邻两点的距离的和，加上末尾与首位的距离，便是边和的两倍
动态删除插入，平衡树，可以借助STL
前置知识：
STL平衡树：「LuoguP3369」 【模板】普通平衡树 （用vector乱搞平衡树 By qwerta
STL set：【C++ STL】Set和Multiset
STL迭代器：C++迭代器的使用和操作总结 C++ 迭代器运算
代码
1 /*************************
2 User:Mandy.H.Y
3 Language:
4 Algorithm:
5 Score:
6 *************************/
7
8 //动态插入删除，平衡树，
9 //算了，用set ^v^
10 //还可以用multiset,vactor
11 //都练练啦
12
13 #include<bits/stdc++.h>
14
15 using namespace std;
16
17 const int maxn = 1e5 + 5;
18
19 int n,m,dfn[maxn],tot,last,rev[maxn];
20 int size,first[maxn];
21 long long dis[maxn];
22 long long ans;//long long
23 int father[maxn],top[maxn],cnt[maxn],dep[maxn];
24 set<int>s;
25
26 struct Edge{
27 int v,nt,w;
28 }edge[maxn << 1];
29
30 template<class T>inline void read(T &x){
31 x = 0;bool flag = 0;char ch = getchar();
32 while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
33 while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
34 if(flag)x = -x;
35 }
36
37 template<class T>void putch(const T x){
38 if(x > 9) putch(x / 10);
39 putchar(x % 10 | 48);
40 }
41
42 template<class T>void put(const T x){
43 if(x < 0) putchar('-'),putch(-x);
44 else putch(x);
45 }
46
47 void file(){
48 freopen("10132.in","r",stdin);
49 // freopen("10132.out","w",stdout);
50 }
51
52 void eadd(int u,int v,int w){
53 edge[ ++ size].v = v;
54 edge[size].w = w;
55 edge[size].nt = first[u];
56 first[u] = size;
57 }
58
59 void readdata(){
60
61 read(n);
62
63 for(int i = 1;i < n;i ++ ){
64 int u,v,w;
65 read(u);read(v);read(w);
66 eadd(u,v,w);eadd(v,u,w);
67 }
68
69 read(m);
70 }
71
72 void dfs(int u,int f,int d){
73
74 dfn[u] = ++tot;rev[tot] = u;
75 father[u] = f;dep[u] = d;
76 top[u] = u;cnt[u] = 1;
77 int mcnt = 0,son = 0;
78
79 for(int i = first[u];i;i = edge[i].nt){
80 int v = edge[i].v;
81 int w = edge[i].w;
82 if(v == f) continue;
83 dis[v] = dis[u] + w;
84 dfs(v,u,d + 1);
85 cnt[u] += cnt[v];
86 if(mcnt < cnt[v]){
87 mcnt = cnt[v];
88 son = v;
89 }
90 }
91
92 if(son) top[son] = u;
93
94 }
95
96 int find(int x){
97 return top[x] == x ? x : top[x] = find(top[x]);
98 }
99
100 int LCA(int x,int y){
101 if(find(x) == find(y)) return dep[x] < dep[y] ? x : y;
102 else return dep[top[x]] < dep[top[y]] ? LCA(x,father[top[y]]) : LCA(y,father[top[x]]);
103 //又打错模板
104 }
105
106 inline set<int>::iterator Left(set<int>::iterator u){
107 set<int>::iterator l;
108 if(u == s.begin()) l = --s.end();
109 else l = --u;
110 return l;
111 }
112
113 inline set<int>::iterator Right(set<int>::iterator u){
114 set<int>::iterator r;
115 if(u == --s.end()) r = s.begin();
116 else r = ++u;
117 return r;
118 } //还是打包比较稳妥
119 void work(){
120
121 dfs(1,0,1);
122
123 while(m -- ){
124 char opt = getchar();
125 int x;
126 while(opt != '+' && opt != '-' && opt != '?') opt = getchar();
127 switch(opt){
128
129 case '+':{
130 read(x);
131
132 if(s.size()){//判空
133
134 set<int> :: iterator u = s.lower_bound(dfn[x]),l;
135
136 if(u == s.end()) u = s.begin();
137 //u是后一个
138 //l是前一个
139 int t = *u;//防止u改变
140 l = Left(u);
141
142 ans -= (dis[rev[t]] + dis[rev[*l]] - 2 * dis[LCA(rev[*l],rev[t])]);
143 ans += (dis[rev[*l]] + dis[x] - 2 * dis[LCA(x,rev[*l])]);
144 ans += (dis[rev[t]] + dis[x] - 2 * dis[LCA(x,rev[t])]);
145
146 }
147 s.insert(dfn[x]);
148 break;
149 }
150
151 case '-':{
152 read(x);
153 if(s.size()){
154 set<int> :: iterator u = s.find(dfn[x]),l,r;
155
156 l = Left(u);
157
158 r = Right(u);
159
160
161 ans -= (dis[rev[*l]] + dis[x] - 2 * dis[LCA(x,rev[*l])]);
162 ans -= (dis[rev[*r]] + dis[x] - 2 * dis[LCA(x,rev[*r])]);
163 ans += (dis[rev[*r]] + dis[rev[*l]] - 2 * dis[LCA(rev[*l],rev[*r])]);
164
165 }
166 s.erase(dfn[x]);
167 break;
168 }
169
170 default:{
171
172 put(ans / 2);
173 puts("");
174 break;
175
176 }
177 }
178 }
179 }
180
181 int main(){
182 // file();
183 readdata();
184 work();
185 return 0;
186 }
View Code