BZOJ2286 消耗战

发表于

  题意:一棵$n$个点，边带权的树，$m$次询问，每次给出k个关键点，求割掉最小代价的边使1号点不能到达任何关键点。

  很裸的树形dp。但是数据范围太大了，承担不起$O(nm)$的复杂度。
  这个时候就需要考虑虚树了。
  什么是虚树?sengxian的博客讲得很好，这里就不多说了。
  这是我的第一道虚树题。通过这道题也能看出很多细节。虚树的复杂度是时刻都必须要算准、保证好的。经常因为一些数组的初始化等问题使得复杂度直接回到了$O(nm)$。比如虚树的邻接表head数组初始化必须要记时间戳，将当前要用的点head清0，而不能直接调用memset。又比如这道题的dp决策，关键点和非关键点的决策是不同的。那么我们如何记录一个点是不是关键点?开数组的话显然初始化又成了问题。
  对于这道题，我们发现在一个关键点下方的关键点dp值是没有任何意义的。所以我们在建虚树的时候就要首先预处理去掉这一类点。这样建出的虚树中关键点均为叶子，于是就不用担心什么了。
  还有一点，建出虚树后的一条边等于原图的一条路径，那么边权怎么办?这道题中我们可以规避这个问题。令$mine[u]$为u到1号点路径中最小的边权，仅仅利用这个东西我们就能进行dp了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define erep(i, u) for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
#define ms(a, b) memset(a, b, sizeof a)
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline T& read(T& x)
{
    static char c; bool flag = 0;
    while(!isdigit(c = getchar())) if(c == '-') flag = 1;
    for(x = c - '0'; isdigit(c = getchar()); (x *= 10) += c - '0');
    if(flag) x = -x; return x;
}
typedef long long LL;
const int maxn = 250010;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
int n, m;
int head[maxn], nxt[maxn << 1], to[maxn << 1], e;
LL w[maxn << 1];
void ae(int x, int y, LL c) { to[++e] = y; nxt[e] = head[x]; head[x] = e; w[e] = c; }
namespace HLD
{
    int cur, fa[maxn], dep[maxn], dfn[maxn], top[maxn], son[maxn], sz[maxn];
    LL mine[maxn];
    void dfs1(int u)
    {
        sz[u] = 1; son[u] = 0;
        erep(i, u) if(v != fa[u])
        {
            fa[v] = u; dep[v] = dep[u] + 1; mine[v] = min(mine[u], w[i]);
            dfs1(v); if(sz[v] > sz[son[u]]) son[u] = v;
            sz[u] += sz[v];
        }
    }
    void dfs2(int u, int g)
    {
        dfn[u] = ++cur; top[u] = g;
        if(son[u]) dfs2(son[u], g);
        erep(i, u) if(v != fa[u] && v != son[u]) dfs2(v, v);
    }
    int LCA(int u, int v)
    {
        while(top[u] != top[v]) (dep[top[u]] > dep[top[v]] ? u = fa[top[u]] : v = fa[top[v]]);
        return dep[u] < dep[v] ? u : v;
    }
}
using namespace HLD;
namespace vtree
{
    int head[maxn], nxt[maxn << 1], to[maxn << 1], e, Time[maxn], cur;
    void ae(int x, int y)
    {
        if(Time[x] != cur)
        {
            head[x] = 0;
            Time[x] = cur;
        }
        to[++e] = y; nxt[e] = head[x]; head[x] = e;
    }
    bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
    void build(int p[], int tot)
    {
        ++cur; e = 0;
        static int stk[maxn]; int top = 0;
        sort(p + 1, p + tot + 1, cmp); int tmp = 1;
        rep(i, 2, tot) if(LCA(p[i], p[tmp]) != p[tmp]) p[++tmp] = p[i];
        tot = tmp;
        stk[++top] = 1;
        rep(i, 1, tot)
        {
            int u = p[i], lca = LCA(u, stk[top]);
            if(lca == stk[top]) stk[++top] = u;
            else
            {
                while(top >= 2 && dep[stk[top - 1]] >= dep[lca])
                {
                    ae(stk[top], stk[top - 1]), ae(stk[top - 1], stk[top]);
                    --top;
                }
                if(stk[top] != lca)
                {
                    ae(lca, stk[top]), ae(stk[top], lca);
                    stk[top] = lca;
                }
                stk[++top] = u;
            }
        }
        rep(i, 1, top - 1) ae(stk[i], stk[i + 1]), ae(stk[i + 1], stk[i]);
    }
    LL dp(int u, int pre)
    {
        LL f = 0;
        erep(i, u) if(v != pre) f += min(dp(v, u), mine[v]);
        return !f ? INF : f;
    }
}
int a[maxn], k;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
    read(n); int u, v; LL c;
    rep(i, 1, n - 1) read(u), read(v), read(c), ae(u, v, c), ae(v, u, c);
    mine[1] = INF, dfs1(1); dfs2(1, 1);
    read(m);
    while(m--)
    {
        read(k);
        rep(i, 1, k) read(a[i]);
        vtree::build(a, k);
        printf("%lld\n", vtree::dp(1, 0));
    }
    return 0;
}