题目描述
在一场战争中，战场由(n)岛屿和(n-1)个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为(1)的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他(k)个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到(1)号岛屿上）。不过侦查部门还发现了这台机器只能够使用(m)次，所以我们只需要把每次任务完成即可。
输入格式：
第一行一个整数(n)，代表岛屿数量。
接下来(n-1)行，每行三个整数(u),(v),(w)，代表(u)号岛屿和(v)号岛屿由一条代价为(c)的桥梁直接相连，保证(1<=u,v<=n)且(1<=c<=100000)。
第(n+1)行，一个整数(m)，代表敌方机器能使用的次数。
接下来(m)行，每行一个整数(ki)，代表第(i)次后，有(ki)个岛屿资源丰富，接下来(k)个整数(h1,h2,…hk)，表示资源丰富岛屿的编号。
输出格式：
输出有(m)行，分别代表每次任务的最小代价。
【数据规模和约定】
对于(10\%)的数据，(2<=n<=10,1<=m<=5,1<=ki<=n-1)
对于(20\%)的数据，(2<=n<=100,1<=m<=100,1<=ki<=min(10,n-1))
对于(40\%)的数据，(2<=n<=1000,m>=1,sigma(ki)<=500000,1<=ki<=min(15,n-1))
对于(100\%)的数据，(2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1)
题目中(k)的总数有(500000),显然虚树优化树形(DP).因为是第一次写虚树所以出了不少(bug),这里来总结一下怎么写虚树.
首先,你要能建立出树形(DP)的朴素模型
在此基础上,由于询问点数和有限,所以我们并不需要对每次询问都(O(N))(DP)回答.这里我们进行一次(DFS)的预处理,只抽出有效信息的一颗浓缩的树.那么关键就在怎么把它抽出来了.
对这个题,我们可以记录一个根节点到每个节点的最窄部分.然后对询问点按照(dfs)序排序.排序过后,对每两个(dfs)序相邻节点求(lca)扔进要用的点里.(可以口胡得到:这样一定涵盖所有必要的(LCA))再按(dfs)序排一次序,然后就可以愉快地建树(DP)啦.
Code:
#include <bits/stdc++.h>
#define int long long
#define N 250010
using namespace std;
int n, m, k, u, v, w, cnt, val[N], head[N];
int ss[N << 1], sta[N << 1], deep[N], ff[N][22], done[N];
struct edge {
int nxt, to, w;
}e[N << 1];
void add_edge (int from, int to, int val) {
e[++cnt].nxt = head[from];
e[cnt].to = to;
e[cnt].w = val;
head[from] = cnt;
}
int dfn[N], low[N], _dfn = 0;
void pre (int u, int fa) {
dfn[u] = ++_dfn;
deep[u] = deep[fa] + 1;
ff[u][0] = fa;
for (int i = 1; (1 << i) <= deep[u]; ++i) {
ff[u][i] = ff[ff[u][i - 1]][i - 1];
}
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != fa) {
val[v] = min (val[u], e[i].w);
pre (v, u);
// printf ("val[%lld] = min (%lld, %lld)
", v, val[u], e[i].w);
}
}
low[u] = _dfn;
}
bool cmp (const int &lhs, const int &rhs) {
return dfn[lhs] < dfn[rhs];
}
int lca (int u, int v) {
// printf ("lca (%lld, %lld) = ", u, v);
if (deep[u] < deep[v]) swap (u, v);
for (int i = 20; i >= 0; --i) {
if (deep[ff[u][i]] >= deep[v]) {
u = ff[u][i];
}
}
if (u == v) return u;
for (int i = 20; i >= 0; --i) {
if (ff[u][i] != ff[v][i]) {
u = ff[u][i];
v = ff[v][i];
}
}
//printf ("%lld
", ff[u][0]);
return ff[u][0];
}
int get_ans (int u, int fa) {
if (done [u]) return val[u];
int res = 0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != fa) {
res += get_ans (v, u);
}
}
return min (res, val[u]);
}
signed main () {
//freopen ("2495.in", "r", stdin);
scanf ("%lld", &n);
for (int i = 1; i < n; ++i) {
scanf ("%lld %lld %lld", &u, &v, &w);
add_edge (u, v, w);
add_edge (v, u, w);
}
memset (val, 0x3f, sizeof (val));
pre (1, 0);
/*
for (int i = 1; i <= n; ++i) {
printf ("node = %lld, val = %lld, low = %lld, dfn = %lld
", i, val[i], low[i], dfn[i]);
} */
memset (head, 0, sizeof (head));
scanf ("%lld", &m);
for (int i = 1; i <= m; ++i) {
// printf ("ask = %lld
", i);
scanf ("%lld", &k);
for (int j = 1; j <= k; ++j) {
scanf ("%lld", &ss[j]);
done[ss[j]] = true;
}
sort (ss + 1, ss + 1 + k, cmp);
for (int j = k; j > 1; --j) {
ss[++k] = lca (ss[j], ss[j - 1]);
}
ss[++k] = 1;
sort (ss + 1, ss + 1 + k, cmp);
k = unique (ss + 1, ss + 1 + k) - ss - 1;
int top = 0; cnt = 0;
for (int j = 1; j <= k; ++j) {
while (top && low[sta[top]] < dfn[ss[j]]) --top;
add_edge (sta[top], ss[j], val[j]);
add_edge (ss[j], sta[top], val[j]);
sta[++top] = ss[j];
}
get_ans (1, 0);
//print_tree (1, 0);
printf ("%lld
", get_ans (1, 0));
for (int j = 1; j <= k; ++j) {
//printf ("dp[%lld] = %lld
", ss[j], dp[ss[j]]);
done[ss[j]] = false, head[ss[j]] = 0;
}
}
}