loj 10132 异象石

题目

传送门：loj10132

在 Adera 的异时空中有一张地图。这张地图上有 N 个点，有N-1 条双向边把它们连通起来。起初地图上没有任何异象石，在接下来的 M 个时刻中，每个时刻会发生以下三种类型的事件之一：

地图的某个点上出现了异象石（已经出现的不会再次出现）；
地图某个点上的异象石被摧毁（不会摧毁没有异象石的点）；
向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。

请你作为玩家回答这些问题。下图是一个例子，灰色节点表示出现了异象石，加粗的边表示被选为连通异象石的边集。

第一行有一个整数 N，表示点的个数；

接下来 N-1 行每行三个整数 x,y,z，表示点 x 和 y 之间有一条长度为 z 的双向边；

第 N+1 行有一个正整数 M；

接下来 M 行每行是一个事件，事件是以下三种格式之一：

+ x：表示点 x 上出现了异象石；
- x：表示点 x 上的异象石被摧毁；
?：表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。

对于每个 ? 事件，输出一个整数表示答案。

样例输入

样例输出

对于100%的数据，1 ≤ n, m ≤ 10⁵, 1 ≤ x, y ≤ n, x ≠ y, 1 ≤ z ≤ 10⁹。

分析

发现按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

非做顽石不可，哪管他敬仰暗唾

loj 10132 异象石

题目

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

分析

代码