Zth's Blog

记录学习路上的点滴

0%

虚树

发表于 分类于

OI Wiki

代码

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>

int n, m;
struct Edge
{
    int from, to, next, cost;
};
struct Al
{
    int tot;
    int head[252345];
    Edge edge[512345];

    void Addedge(int u, int v, int e)
    {
        edge[++ tot] = (Edge){u, v, head[u], e};

        head[u] = tot;
    }
} ot, vt; // 邻接表， ot是原图， vt是虚树图
int dfn[252345], no; // dfs序
int pa[252345][21], pb[252345][21]; // pa表示上跳的点， pb表示上跳到点的路径中最短的一条边的边权
int dep[252345]; // 深度
struct Node
{
    int num, d;

    bool operator < (Node tmp) const
    {
        return d < tmp.d;
    }
} node[252345];
std:: stack<int> stk;
bool key[252345]; // 是否为键值
long long dp[252345];

void Pre(int u, int f, int w) // lca和路径的预处理
{
    dfn[u] = ++ no;
    dep[u] = dep[f] + 1;
    pa[u][0] = f;
    pb[u][0] = w;

    for(int i = 1; i <= 20; i ++)
        pa[u][i] = pa[pa[u][i - 1]][i - 1],
                pb[u][i] = std:: min(pb[u][i - 1], pb[pa[u][i - 1]][i - 1]);

    for(int i = ot.head[u]; i; i = ot.edge[i].next)
    {
        int v = ot.edge[i].to, e = ot.edge[i].cost;

        if(v == f) continue;

        Pre(v, u, e);
    }
}

int Lca(int x, int y) // lca
{
    if(dep[x] < dep[y])
        x ^= y, y ^= x, x ^= y;

    for(int i = 20; i >= 0; i --)
        if(dep[pa[x][i]] >= dep[y])
            x = pa[x][i];

    if(x == y) return x;

    for(int i = 20; i >= 0; i --)
        if(pa[x][i] != pa[y][i])
            x = pa[x][i], y = pa[y][i];

    return pa[x][0];
}

int Find(int x, int y) // 找到x到y的路径中最短的一条边
{
    int mn = 1e5 + 1;

    for(int i = 20; i >= 0; i --)
        if(pa[x][i] && dep[pa[x][i]] >= dep[y])
            mn = std:: min(mn, pb[x][i]), x = pa[x][i];

    return mn;
}

void Dp(int u, int f)
{
    dp[u] = 0;

    for(int i = vt.head[u]; i; i = vt.edge[i].next)
    {
        int v = vt.edge[i].to, e = vt.edge[i].cost;

        Dp(v, u);

        if(key[v])
            dp[u] += e;
        else
            dp[u] += std:: min(dp[v], 1LL * e);
    }
}

void Debug(int u, int f)
{
    for(int i = vt.head[u]; i; i = vt.edge[i].next)
    {
        int v = vt.edge[i].to, e = vt.edge[i].cost;

        if(v == f) continue;

        printf("%d -> %d %d\n", u, v, e);

        Debug(v, u);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n - 1; i ++)
    {
        int u, v, e;
        scanf("%d%d%d", &u, &v, &e);

        ot.Addedge(u, v, e);
        ot.Addedge(v, u, e);
    }

    Pre(1, 0, 0);
    stk.push(1);

    scanf("%d", &m);
    for(int i = 1; i <= m; i ++)
    {
        int k;
        scanf("%d", &k);

        for(int j = 1; j <= k; j ++)
        {
            scanf("%d", &node[j].num);

            node[j].d = dfn[node[j].num];
            key[node[j].num] = true;
        }

        vt.tot = 0;
        vt.head[1] = 0;
        std:: sort(node + 1, node + k + 1);

        for(int j = 1; j <= k; j ++)
        {
            int lca = Lca(stk.top(), node[j].num);

            while(dfn[stk.top()] > dfn[lca])
            {
                int tmp = stk.top();
                stk.pop();

                if(dfn[stk.top()] > dfn[lca])
                    vt.Addedge(stk.top(), tmp, Find(tmp, stk.top()));
                else if(stk.top() == lca) // lca在栈中， 直接连边
                    vt.Addedge(lca, tmp, Find(tmp, lca));
                else // lca不在栈中， 添加lca然后向lca连边
                {
                    stk.push(lca);
                    vt.head[lca] = 0;

                    vt.Addedge(lca, tmp, Find(tmp, lca));
                }
            }

            stk.push(node[j].num); // 每个点入栈时清空其邻接表
            vt.head[node[j].num] = 0;
        }

        while(stk.size() > 1)
        {
            int tmp = stk.top();
            stk.pop();

            vt.Addedge(stk.top(), tmp, Find(tmp, stk.top()));
        }

        Dp(1, 0);
        printf("%lld\n", dp[1]);
        //Debug(1, 0);

        for(int j = 1; j <= k; j ++) key[node[j].num] = false;
    }

    return 0;
}