CTime_Pup_314

不能再颓废了

0%

[SDOI2011]消耗战

发表于 更新于 分类于 阅读次数： Valine：

题面描述

给定关键点，求树的最小割

题解

虚树模板题，虚树是用来解决多次询问，但关键点总数有限的优化方法，就是将关键点及其 \(LCA\) 提取出来在进行 \(DP\)

具体来说，我们先将关键点按 \(dfn\) 排序，依次加入一个栈中，这个栈维护了从根到栈顶的一条链

设加入节点为 \(p\) 则分如下情况讨论

若 \(LCA(p,\ S_{top})\ =\ S_{top}\) 说明 \(p\) 仍在链上，直接入栈

反之，则说明已经到另外一颗子树上了 不断弹出栈顶直到 \(dfn_{S_{top-1}}<dfn_{lca}\) 并且 连边 \((S_{top-1},\ S_{top})\) 把 \(S_{top}\) 到 \(lca\) 的点提取出来

如果 \(S_{top}\ne lca\) 则连边 \((lca,\ S_{top})\) 将栈顶变为 \(lca\)

然后，\(p\) 再入栈

最后在处理下栈中剩下的链即可

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
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
#include <vector>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 5e5+5;
struct Edge
{
    int next, to, w;
    Edge(int next = 0, int to = 0, int w = 0):next(next), to(to), w(w) {};
}edge[N<<1];
int head[N], tot;
void _add(int x, int y, int z) { edge[++tot] = Edge(head[x], y, z); head[x] = tot; }
void add(int x, int y, int z) { _add(x, y, z); _add(y, x, z); }
int n, m, q, ac[20][N], d[N], nfd[N], dfn[N], t, p[N];
int64 f[N];
void dfs(int x, int fa)
{
    ac[0][x] = fa; dfn[++t] = x; nfd[x] = t; d[x] = d[fa]+1;
    for(int i = 1; i < 20; ++i) ac[i][x] = ac[i-1][ac[i-1][x]];
    for(int i = head[x]; i; i = edge[i].next)
    {
        int y = edge[i].to, z = edge[i].w;
        if(y == fa) continue; 
        f[y] = min(f[x], 1ll*z); dfs(y, x); 
    }
}
int LCA(int x, int y)
{
    if(d[x] > d[y]) swap(x, y);
    for(int i = 19; ~i; --i)
        if(d[ac[i][y]] >= d[x]) y = ac[i][y];
    if(x == y) return x;
    for(int i = 19; ~i; --i) 
        if(ac[i][x] != ac[i][y]) x = ac[i][x], y = ac[i][y];
    return ac[0][x]; 
}
bool cmp(int x, int y) { return nfd[x] < nfd[y]; }
namespace vtree
{
int s[N], top, cov[N];
vector<int> edge[N];
void add(int x, int y) { edge[x].push_back(y); }
void insert(int x)
{
    int lca = LCA(x, s[top]);
    if(lca == s[top]) return void(s[++top] = x);
    while(top > 1&&nfd[s[top-1]] >= nfd[lca]) add(s[top-1], s[top]), --top;
    if(s[top] != lca) add(lca, s[top]), s[top] = lca;
    s[++top] = x;  
}
void build()
{
    s[top = 1] = 1;
    for(int k = 1; k <= m; ++k) cov[p[k]] = 1, insert(p[k]); 
    while(top > 1) add(s[top-1], s[top]), --top;
}
int64 dp(int x)
{
    int64 ret = 0; 
    for(int i = 0; i < edge[x].size(); ++i) 
        ret += dp(edge[x][i]);
    edge[x].clear();
    if(!cov[x]) return min(ret, f[x]);
    cov[x] = 0; return f[x];
}
}
int main()
{
    n = read();
    for(int i = 1; i < n; ++i)
    {
        int x = read(), y = read(), z = read();
        add(x, y, z); 
    }
    q = read(); memset(f, 0x3f, sizeof(f)); dfs(1, 0); 
    while(q--)
    {
        m = read();
        for(int k = 1; k <= m; ++k) p[k] = read();
        sort(p+1, p+1+m, cmp); vtree::build(); 
        printf("%lld\n", vtree::dp(1));
    }
    return 0;
}