异象石 CH Round #56 - 国庆节欢乐赛
描述
Adera 是 Microsoft 应用商店中的一款解谜游戏.
异象石是进入 Adera 中异时空的引导物, 在 Adera 的异时空中有一张地图. 这张地图上有 N 个点, 有 N-1 条双向边把它们连通起来. 起初地图上没有任何异象石, 在接下来的 M 个时刻中, 每个时刻会发生以下三种类型的事件之一:
1. 地图的某个点上出现了异象石 (已经出现的不会再次出现);
2. 地图某个点上的异象石被摧毁 (不会摧毁没有异象石的点);
3. 向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少.
请你作为玩家回答这些问题.
输入格式
第一行有一个整数 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
数据范围与约定
对于 30% 的数据, 1 ≤ n, m ≤ 1000.
对于另 20% 的数据, 地图是一条链, 或者一朵菊花.
对于 100% 的数据, 1 ≤ n, m ≤ 10^5, 1 ≤ x, y ≤ n, x ≠ y, 1 ≤ z ≤ 10^9.
题解
把有异象石的点按照其 DFS 序大小写作一个环形序列, 该序列中相邻的数的距离之和就是答案的 2 倍.
用 set 维护这个序列, 用一个变量记录答案, 插入 or 摧毁时在序列中插入 or 删除数, 并更改答案即可. 求距离可以用倍增 lca.
时间复杂度 \(O((n+m)\log n)\)
- #include<bits/stdc++.h>
- #define rg register
- #define il inline
- #define co const
- template<class T>il T read(){
- rg T data=0,w=1;rg char ch=getchar();
- for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
- for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
- return data*w;
- }
- template<class T>il T read(rg T&x) {return x=read<T>();}
- typedef long long ll;
- using namespace std;
- typedef pair<int,int> pii;
- co int N=1e5+1;
- int n,m,t,f[N][18],dep[N],dfn[N],tot;
- vector<pii> e[N];
- ll d[N],ans;
- set<pii> st;
- typedef set<pii>::iterator it;
- void dfs(int x){
- dfn[x]=++tot;
- for(int i=0,y;i<e[x].size();++i){
- if(dep[y=e[x][i].first]) continue;
- dep[y]=dep[x]+1;
- d[y]=d[x]+e[x][i].second;
- f[y][0]=x;
- for(int j=1;j<=t;++j) f[y][j]=f[f[y][j-1]][j-1];
- dfs(y);
- }
- }
- int lca(int x,int y){
- if(dep[x]>dep[y]) swap(x,y);
- for(int i=t;i>=0;--i)
- if(dep[f[y][i]]>=dep[x]) y=f[y][i];
- if(x==y) return x;
- for(int i=t;i>=0;--i)
- if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
- return f[x][0];
- }
- il ll path(int x,int y){
- return d[x]+d[y]-2*d[lca(x,y)];
- }
- il void insert(int x){
- st.insert(pii(dfn[x],x));
- it l=st.find(pii(dfn[x],x));
- l=l==st.begin()?--st.end():--l;
- it r=st.find(pii(dfn[x],x));
- r=r==--st.end()?st.begin():++r;
- ans-=path(l->second,r->second);
- ans+=path(l->second,x)+path(x,r->second);
- }
- il void remove(int x){
- it l=st.find(pii(dfn[x],x));
- l=l==st.begin()?--st.end():--l;
- it r=st.find(pii(dfn[x],x));
- r=r==--st.end()?st.begin():++r;
- ans-=path(l->second,x)+path(x,r->second);
- ans+=path(l->second,r->second);
- st.erase(pii(dfn[x],x));
- }
- int main(){
- read(n);
- for(int i=1,x,y,z;i<n;++i){
- read(x),read(y),read(z);
- e[x].push_back(pii(y,z)),e[y].push_back(pii(x,z));
- }
- t=log(n)/log(2)+1;
- dep[1]=1,dfs(1);
- for(read(m);m--;){
- char s[2];scanf("%s",s);
- if(s[0]=='?') printf("%lld\n",ans/2);
- else{
- int x=read<int>();
- s[0]=='+'?insert(x):remove(x);
- }
- }
- return 0;
- }
3991: [SDOI2015] 寻宝游戏
- Time Limit: 40 Sec Memory Limit: 128 MB
- Submit: 2219 Solved: 1133
- [Submit][Status][Discuss]
- Description
小 B 最近正在玩一个寻宝游戏, 这个游戏的地图中有 N 个村庄和 N-1 条道路, 并且任何两个村庄之间有且仅有一条路径可达. 游戏开始时, 玩家可以任意选择一个村庄, 瞬间转移到这个村庄, 然后可以任意在地图的道路上行走, 若走到某个村庄中有宝物, 则视为找到该村庄内的宝物, 直到找到所有宝物并返回到最初转移到的村庄为止. 小 B 希望评测一下这个游戏的难度, 因此他需要知道玩家找到所有宝物需要行走的最短路程. 但是这个游戏中宝物经常变化, 有时某个村庄中会突然出现宝物, 有时某个村庄内的宝物会突然消失, 因此小 B 需要不断地更新数据, 但是小 B 太懒了, 不愿意自己计算, 因此他向你求助. 为了简化问题, 我们认为最开始时所有村庄内均没有宝物
Input
第一行, 两个整数 N,M, 其中 M 为宝物的变动次数.
接下来的 N-1 行, 每行三个整数 x,y,z, 表示村庄 x,y 之间有一条长度为 z 的道路.
接下来的 M 行, 每行一个整数 t, 表示一个宝物变动的操作. 若该操作前村庄 t 内没有宝物, 则操作后村庄内有宝物; 若该操作前村庄 t 内有宝物, 则操作后村庄内没有宝物.
Output
M 行, 每行一个整数, 其中第 i 行的整数表示第 i 次操作之后玩家找到所有宝物需要行走的最短路程. 若只有一个村庄内有宝物, 或者所有村庄内都没有宝物, 则输出 0.
- Sample Input
- 4 5
- 1 2 30
- 2 3 50
- 2 4 60
- 2
- 3
- 4
- 2
- 1
- Sample Output
- 0
- 100
- 220
- 220
- 280
- HINT
- 1<=N<=100000
- 1<=M<=100000
对于全部的数据, 1<=z<=10^9
Source
Round 1 感谢 yts1999 上传
- [Submit][Status][Discuss]
- ?
- HOMEBack
题解
这个每条边要走两次, 选他们构成的虚树上的那个点都无所谓. 实际上就是上一道题, 只不过答案不用除以 2.
来源: http://www.bubuko.com/infodetail-3097928.html