一道虛樹題，但是做完之后發現跟虛樹半點關系沒有，反而更像思維題。

首先默認讀者會虛樹，然后會發現這道題有一個樸素做法就是對于每一次操作完之后的點我們都建一棵虛樹，然后這個虛樹上面的 DP 是簡單的。

然后這個復雜度最壞是 $O(nm)$ 的，顯然會炸，于是我們要想想辦法。

發現實際上我們沒有必要做一遍 DP，在我們求出了原樹的 dfs 序之后其實這玩意就很好搞了。

接下來以加入一個點為例，我們將其丟進目前關鍵點序列里面之后發現實際上這個點只會影響到 dfs 序在這個點之前的和在這個點之后的，就像這樣：

如圖，$x,y$ 是兩個 dfs 序與 $z$ 最接近的點，然后發現只需要將紅色路徑改成藍色路徑就可以了，而且可以證明這個方式一定是對答案影響最小的。

綜上我們根本沒必要建虛樹，只需要用個 set 維護關鍵點序列就好了，弄個倍增或者樹上差分之類的求一下路徑距離即可。

GitHub：CodeBase-of-Plozia。

Code：

/* ========= Plozia =========Author:PloziaProblem:P3320 [SDOI2015]尋寶游戲Date:2021/12/14 ========= Plozia ========= */#include <bits/stdc++.h> using std::set;typedef long long LL; const int MAXN = 1e5 + 5; int n, q, Head[MAXN], cnt_Edge = 1, fa[MAXN][21], dep[MAXN], dfn[MAXN], ys[MAXN]; LL g[MAXN][21], ans; bool book[MAXN]; struct node { int To, val, Next; } Edge[MAXN << 1]; set <int> s; set <int> :: iterator it1, it2, it3;int Read() {int sum = 0, fh = 1; char ch = getchar();for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = sum * 10 + (ch ^ 48);return sum * fh; } int Max(int fir, int sec) { return (fir > sec) ? fir : sec; } int Min(int fir, int sec) { return (fir < sec) ? fir : sec; } void add_Edge(int x, int y, int z) { ++cnt_Edge; Edge[cnt_Edge] = (node){y, z, Head[x]}; Head[x] = cnt_Edge; }void dfs(int now, int father) {fa[now][0] = father; dep[now] = dep[father] + 1; dfn[now] = ++dfn[0]; ys[dfn[0]] = now;for (int i = Head[now]; i; i = Edge[i].Next){int u = Edge[i].To;if (u == father) continue ;g[u][0] = Edge[i].val; dfs(u, now);} }void init() {for (int j = 1; j <= 20; ++j)for (int i = 1; i <= n; ++i){fa[i][j] = fa[fa[i][j - 1]][j - 1];g[i][j] = g[i][j - 1] + g[fa[i][j - 1]][j - 1];} }LL Ask(int x, int y) {LL val = 0;if (dep[x] < dep[y]) std::swap(x, y);for (int i = 20; i >= 0; --i)if (dep[fa[x][i]] >= dep[y]) { val += g[x][i]; x = fa[x][i]; }if (x == y) return val;for (int i = 20; i >= 0; --i)if (fa[x][i] != fa[y][i]) { val += g[x][i] + g[y][i]; x = fa[x][i]; y = fa[y][i]; }return val + g[x][0] + g[y][0]; }int main() {n = Read(), q = Read();for (int i = 1; i < n; ++i){int x = Read(), y = Read(), z = Read();add_Edge(x, y, z); add_Edge(y, x, z);}dfs(1, 1); init();for (int i = 1; i <= q; ++i){int x = Read();if (book[x]){book[x] = 0; it1 = s.lower_bound(dfn[x]); it2 = s.upper_bound(dfn[x]);it3 = s.end(); int p1, p2;if (it1 != s.begin()) p1 = *(--it1); else p1 = *(--it3);if (it2 != s.end()) p2 = *it2; else p2 = *s.begin();ans = ans - Ask(ys[p1], x) - Ask(ys[p2], x) + Ask(ys[p1], ys[p2]);printf("%lld\n", ans); s.erase(dfn[x]);}else{s.insert(dfn[x]); it1 = s.lower_bound(dfn[x]); it2 = s.upper_bound(dfn[x]);book[x] = 1; it3 = s.end(); int p1, p2;if (it1 != s.begin()) p1 = *(--it1); else p1 = *(--it3);if (it2 != s.end()) p2 = *it2; else p2 = *s.begin();ans = ans + Ask(ys[p1], x) + Ask(ys[p2], x) - Ask(ys[p1], ys[p2]);printf("%lld\n", ans);}}return 0; }

總結

以上是生活随笔為你收集整理的P3320 [SDOI2015]寻宝游戏 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。