ybt1554 异象石 题解

· · 个人记录

原题链接

【题目描述】

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

地图的某个点上出现了异象石（已经出现的不会再次出现）；

地图某个点上的异象石被摧毁（不会摧毁没有异象石的点）；

向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。

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

【输入】

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

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

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

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

$−x$ ：表示点 $x$ 上的异象石被摧毁； $?$ ：表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。 ### 【输出】 对于每个 $?$ 事件，输出一个整数表示答案。 ------------ ## 正解： __我们先来分析一下题目__ 题目给出的东西是数，然后会有两种操作，以及询问。 ~~题目思路极其难想，我直接讲正解吧~~ 首先输入，然后设定时间戳——dfn(与Tarjan有点相似)，依次从根节点遍历到叶子结点。 然后对于算出有异象石的点，只要在每次产生异象石时和摧毁异象石时随着维护即可。 话不多说，上代码： ``` #include<bits/stdc++.h> using namespace std; const int MAXN = 100000 + 10; int dfn[MAXN],dep[MAXN]; int fa[MAXN][25]; long long w[MAXN],ans; int n,m,cnt,t ; struct Node{ int next; long long num; bool operator < (const Node& next) const { return num < next.num; } }; struct St{ int tim; int id; bool operator < (const St& next) const { return tim < next.tim; } }; vector<Node> nei[MAXN]; set<St>st; set<St>::iterator it; inline int read() {//快速读入 int f = 1, x = 0; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return f * x; } /*int LCA(int x,int y){ if(dep[x] < dep[y])swap(x,y); for(int i = 20;i >= 0; i--){ if(dep[fa[x][i]] >= dep[y])x = fa[x][i]; } if(x == y)return x; for(int i = 20;i >= 0; i--){ if(fa[x][i] != fa[y][i]){ x = fa[x][i]; y = fa[y][i]; } } return fa[x][0]; }*/ int LCA(int a,int b){ if(dep[a] > dep[b])swap(a,b); for(int i = t;i >= 0; i--){ if(dep[a] <= dep[b] - (1 << i)){ b = fa[b][i]; } } if(a == b){ return a; } for(int i = t;i >= 0; i--){ if(fa[a][i] != fa[b][i]){ a = fa[a][i]; b = fa[b][i]; } } return fa[a][0]; } long long path(int x,int y){ return w[x] + w[y] - (2 * w[LCA(x,y)]); } void dfs(int now) { dfn[now] = ++cnt; int len = nei[now].size(); for(int i = 0;i < len; i++) { int next = nei[now][i].next; if(dep[next])continue; dep[next] = dep[now] + 1; w[next] = w[now] + nei[now][i].num; fa[next][0] = now; for(int j = 1;j <= t; j++) { fa[next][j] = fa[fa[next][j - 1]][j - 1]; } dfs(next); } return ; } void add(int now){ St cur = {dfn[now],now}; st.insert(cur); it = st.find(cur); set<St>::iterator l = it == st.begin() ? --st.end() : --it; it = st.find(cur); set<St>::iterator r = it == --st.end() ? st.begin() : ++it; it = st.find(cur); ans -= path((*l).id,(*r).id); ans += path((*l).id,(*it).id) + path((*it).id,(*r).id); } void move(int now){ St cur = {dfn[now],now}; it = st.find(cur); set<St>::iterator l = it == st.begin() ? --st.end() : --it; it = st.find(cur); set<St>::iterator r = it == --st.end() ? st.begin() : ++it; it = st.find(cur); ans += path((*l).id,(*r).id); ans -= path((*l).id,(*it).id) + path((*it).id,(*r).id); st.erase(cur); } int main() { n = read(); for(int i = 1;i < n; i++){ int x = read(),y = read(); long long z; cin>>z; Node x_to = {y,z}; Node y_to = {x,z}; nei[x].push_back(x_to); nei[y].push_back(y_to); } dep[1] = 1; t = log(n) / log(2); //t = 25; dfs(1); m = read(); for(int i = 1;i <= m; i++){ char c; cin>>c; if(c == '?') { cout<<ans / 2<< "\n"; }else { int tot = read(); c == '+' ? add(tot) : move(tot); } } return 0; } ```