【bzoj3991】[SDOI2015]寻宝游戏 树链的并+STL-set
2023-09-11 14:22:39 时间
题目描述
给出一棵树,初始每个点都是非必经的。多次改变某个点的必经状态,并询问从任意一个点出发,经过所有必经的点并回到该点的最小路程。
输入
第一行,两个整数N、M,其中M为宝物的变动次数。
接下来的N-1行,每行三个整数x、y、z,表示村庄x、y之间有一条长度为z的道路。
接下来的M行,每行一个整数t,表示一个宝物变动的操作。若该操作前村庄t内没有宝物,则操作后村庄内有宝物;若该操作前村庄t内有宝物,则操作后村庄内没有宝物。
输出
M行,每行一个整数,其中第i行的整数表示第i次操作之后玩家找到所有宝物需要行走的最短路程。若只有一个村庄内有宝物,或者所有村庄内都没有宝物,则输出0。
样例输入
4 5
1 2 30
2 3 50
2 4 60
2
3
4
2
1
样例输出
0
100
220
220
280
题解
树链的并+STL-set
考虑指定某个点为根,如果从根节点出发的话,答案显然是所有必经点到根节点的树链的并的长度*2。
我们维护这个树链的并:把所有点按照dfs序排序,每个点到根的距离减去排序后相邻两点LCA到根的距离就是树链的并的长度。本题由于需要支持插入和删除,因此可以使用STL-set。
但是这并不是最优解。考虑重复经过了哪一段:所有相邻两点LCA中深度最小的到根节点的距离。也即按dfs序排序后第一个点和最后一个点的LCA到根节点的距离。因此再使用set统计一下答案即可。
时间复杂度 $O(n\log n)$
#include <set> #include <cstdio> #define N 100010 using namespace std; typedef long long ll; set<int> s; int head[N] , to[N << 1] , len[N << 1] , next[N << 1] , cnt , fa[N][20] , deep[N] , log[N] , pos[N] , ref[N] , tot , vis[N]; ll dis[N]; inline void add(int x , int y , int z) { to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt; } void dfs(int x) { int i; pos[x] = ++tot , ref[tot] = x; for(i = 1 ; (1 << i) <= deep[x] ; i ++ ) fa[x][i] = fa[fa[x][i - 1]][i - 1]; for(i = head[x] ; i ; i = next[i]) if(to[i] != fa[x][0]) fa[to[i]][0] = x , deep[to[i]] = deep[x] + 1 , dis[to[i]] = dis[x] + len[i] , dfs(to[i]); } inline int lca(int x , int y) { int i; if(deep[x] < deep[y]) swap(x , y); for(i = log[deep[x] - deep[y]] ; ~i ; i -- ) if((1 << i) <= deep[x] - deep[y]) x = fa[x][i]; if(x == y) return x; for(i = log[deep[x]] ; ~i ; i -- ) if((1 << i) <= deep[x] && fa[x][i] != fa[y][i]) x = fa[x][i] , y = fa[y][i]; return fa[x][0]; } int main() { int n , m , i , x , y , z; set<int>::iterator it; ll now = 0; scanf("%d%d" , &n , &m); for(i = 2 ; i <= n ; i ++ ) scanf("%d%d%d" , &x , &y , &z) , add(x , y , z) , add(y , x , z) , log[i] = log[i >> 1] + 1; dfs(1); while(m -- ) { scanf("%d" , &x) , y = z = 0; if(!vis[x]) { it = s.upper_bound(pos[x]); if(it != s.end()) y = ref[*it]; if(it != s.begin()) z = ref[*--it]; if(y) now -= dis[lca(x , y)]; if(z) now -= dis[lca(x , z)]; if(y && z) now += dis[lca(y , z)]; now += dis[x] , vis[x] = 1 , s.insert(pos[x]); } else { now -= dis[x] , vis[x] = 0 , s.erase(pos[x]); it = s.upper_bound(pos[x]); if(it != s.end()) y = ref[*it]; if(it != s.begin()) z = ref[*--it]; if(y) now += dis[lca(x , y)]; if(z) now += dis[lca(x , z)]; if(y && z) now -= dis[lca(y , z)]; } if(s.size() < 2) puts("0"); else printf("%lld\n" , (now - dis[lca(ref[*s.begin()] , ref[*--s.end()])]) << 1); } return 0; }
相关文章
- 【BZOJ3232】圈地游戏(分数规划,网络流)
- 【Luogu3041】视频游戏的连击(AC自动机,动态规划)
- [cocos2d-x]怎样降低cocos2d-x游戏的耗电量?
- 【BZOJ4881】5月月赛D 线段游戏 树状数组+set
- 1063 Set Similarity (25 分)【难度: 一般 / 知识点: STL中set的应用】
- 手把手教你Egret引擎一键发布华为快游戏
- 《Android游戏开发详解》一2.2 设置开发机器
- 《Cocos2d 跨平台游戏开发指南(第2版)》一1.4 访问主场景(MainScene)
- 《HTML5游戏编程核心技术与实战》——2.4 坐标变换
- 二分法(折半查找)的运用之java实现猜数字游戏
- 小学生python游戏编程arcade----基本知识5 自动行走的敌人
- GameFrameWork框架(Unity3D)使用笔记(五)游戏主流程ProcedureMain
- 基于Cocos2dx开发卡牌游戏_松开,这三个国家
- 从0开发游戏引擎之游戏引擎底层数学库实现