引入
$ \color{skyblue} P2495 [SDOI2011] 消耗战 $
题意
给定一颗 $ n $ 个节点的树，每条边有边权。有 $ m $ 次询问，每次询问钦定 $ k $ 个特殊节点，问使得节点 $ 1 $ 不与任何特殊节点相连通所需要删除的最小总边权是多少。
数据范围：
- 对于 \(100\%\) 的数据，\(2\leq n \leq 2.5\times 10^5, 1\leq m\leq 5\times 10^5, \sum k_i \leq 5\times 10^5, 1\leq k_i< n, h_i\neq 1, 1\leq u,v\leq n, 1\leq w\leq 10^5\) 。
思路
首先考虑数据范围较小时怎么做。
显然存在 $ O(n) $ 的线性 $ dp $：
设 $ dp_i $ 表示在以 $ i $ 为根的子树内使得 $ i $ 不与特殊节点联通所需删除最小总边权。
设当前考虑到 $ i $ 的子节点 $ v $
-
若 $ v $ 是特殊节点，$ dp_i = dp_i + w(i, v) $
-
若 $ v $ 不是特殊节点，$ dp_i = dp_i + min(dp_v, w(i, v) $
可以发现，在 $ \sum k_i \leq 5\times 10^5 $ 这样的数据范围下，每次跑一遍线性 $ dp $ 会有很多冗余计算。
所以考虑如何将 $ dp $ 的复杂度降为与 $ k $ 相关。
这时就引入了虚树的概念。
在虚树中，特殊节点以及其两两之间的LCA都被保留，而其他节点则被省略。
如：
(图片来自OI Wiki)
因为特殊节点两两之间的LCA被保留，所以虚树的节点个数最多是 $ 2 \times k $ 个 $ ( k $ 为特殊节点个数 $ ) $ 。
显然，虚树中两点之间的祖先关系并不会改变，所以我们可以在虚树上跑 $ dp $, 而这时 $ dp $ 的时间复杂度就是 $ O(k) $ 的了。
接下来的问题就是如何构造虚树。
目前有两种方法，一是两次排序+LCA连边，二是单调栈建树。
这里只介绍第一种（个人认为代码简单且好理解）
步骤：
-
将特殊节点按 $ dfs $ 序排序。
-
将特殊节点及相邻两项间的 $ LCA $ 放入一个新的数组并去重。
-
对于新数组中的相邻两项 $ x $ 和 $ y $ ，把 $ LCA(x, y) $ 和 $ y $ 连边。
证明
如果 $ x $ 是 $ y $ 的祖先，那么 $ x $ 直接到 $ y $ 连边。因为 $ DFS $ 序保证了 $ x $ 和 $ y $ 的 $ DFS $ 序是相邻的，所以 $ x $ 到 $ y $ 的路径上面没有关键点。
如果 $ x $ 不是 $ y $ 的祖先，那么就把 $ LCA(x, y) $ 当作 $ y $ 的的祖先，根据上一种情况也可以证明 $ LCA(x, y) $ 到 $ y $ 点的路径上不会有关键点。
所以连接 $ LCA(x, y) $ 和 $ y $ 不会遗漏，也不会重复。
另外第一个点没有被一个节点连接会不会有影响呢?因为第一个点一定是这棵树的根，所以不会有影响，所以总边数就是 $ m-1 $ 条。
引自OI-Wiki
模板：
struct Edge {
int nxt, to, w;
};
struct Tree {
int cnt, head[N];
Edge e[N << 1];
void addedge(int u, int v, int w) {
cnt++;
e[cnt].nxt = head[u];
e[cnt].to = v;
e[cnt].w = w;
head[u] = cnt;
}
}v;
void build() {
v.cnt = -1;
k = read();
for(int i = 1; i <= k; i++) h[i] = read(), q[h[i]] = 1;
sort(h + 1, h + 1 + k, cmp);
len = 0;
for(int i = 1; i < k; i++) {
a[++len] = h[i];
a[++len] = lca(h[i], h[i + 1]);
}
a[++len] = h[k];
a[++len] = 1;
sort(a + 1, a + 1 + len, cmp);
len = unique(a + 1, a + 1 + len) - a - 1;
for(int i = 1; i < len; i++) {
int p = lca(a[i], a[i + 1]);
v.addedge(p, a[i + 1], dis(p, a[i + 1]));
}
}
回到题目。
既然建树已经解决了，那这题就可以做了。
注意，对于每组询问都清空全部数组的话时间复杂度仍然会炸，所以就对用过的位置恢复即可。
代码
#include<bits/stdc++.h>
#define int long long
#define Debug puts("Oops!")
using namespace std;
const int N = 6e5 + 5, M = 5e5 + 5;
int n, m, k, len;
int h[N], a[N], q[N];
struct Edge {
int nxt, to, w;
};
struct Tree {
int cnt, head[N];
Edge e[N << 1];
void addedge(int u, int v, int w) {
cnt++;
e[cnt].nxt = head[u];
e[cnt].to = v;
e[cnt].w = w;
head[u] = cnt;
}
}g, v;
int dep[N], dfn[N], tot;
int fat[N][25], d[N][25];
void dfs(int x, int fa) {
dfn[x] = ++tot;
dep[x] = dep[fa] + 1;
for(int i = g.head[x]; ~i; i = g.e[i].nxt) {
int y = g.e[i].to;
if(y == fa) continue ;
fat[y][0] = x;
d[y][0] = g.e[i].w;
dfs(y, x);
}
}
void init() {
for(int i = 1; i <= 19; i++) {
for(int j = 1; j <= n; j++) {
fat[j][i] = fat[fat[j][i - 1]][i - 1],
d[j][i] = min(d[j][i - 1], d[fat[j][i - 1]][i - 1]);
}
}
}
int lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int i = 19; i >= 0; i--)
if(dep[fat[x][i]] >= dep[y])
x = fat[x][i];
if(x == y) return x;
for(int i = 19; i >= 0; i--)
if(fat[x][i] != fat[y][i]) x = fat[x][i], y = fat[y][i];
return fat[x][0];
}
int dis(int x, int y) {//求x到y的路径上的边权最小值
int res = LLONG_MAX;
for(int i = 19; i >= 0; i--)
if(dep[fat[y][i]] >= dep[x])
res = min(res, d[y][i]), y = fat[y][i];
return res;
}
bool cmp(int x, int y) {
return dfn[x] < dfn[y];
}
int f[N];
void dp(int x) {
f[x] = 0;
for(int i = v.head[x]; ~i; i = v.e[i].nxt) {
int y = v.e[i].to;
dp(y);
if(q[y]) f[x] += v.e[i].w;
else f[x] += min(f[y], v.e[i].w);
}
}
inline int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
return x * f;
}
void solve() {
v.cnt = -1;
k = read();
for(int i = 1; i <= k; i++) h[i] = read(), q[h[i]] = 1;
sort(h + 1, h + 1 + k, cmp);
len = 0;
for(int i = 1; i < k; i++) {
a[++len] = h[i];
a[++len] = lca(h[i], h[i + 1]);
}
a[++len] = h[k];
a[++len] = 1;
sort(a + 1, a + 1 + len, cmp);
len = unique(a + 1, a + 1 + len) - a - 1;
for(int i = 1; i < len; i++) {
int p = lca(a[i], a[i + 1]);
v.addedge(p, a[i + 1], dis(p, a[i + 1]));
//删除虚树上的这条边只要删除原树上p到a[i + 1]的路径中的最小边即可
}
dp(1);
cout << f[1] << endl;
for(int i = 1; i < len; i++) v.head[a[i + 1]] = -1, v.head[lca(a[i], a[i + 1])] = -1;
for(int i = 1; i <= k; i++) q[h[i]] = 0;
}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
memset(g.head, -1, sizeof g.head);
memset(v.head, -1, sizeof v.head);
g.cnt = -1;
n = read();
for(int i = 1, u, v, w; i < n; i++) {
u = read(), v = read(), w = read();
g.addedge(u, v, w);
g.addedge(v, u, w);
}
memset(d, 0x7f, sizeof d);
dfs(1, 0);
init();
m = read();
while(m--) solve();
return 0;
}