<虚树+树型DP> SDOI2011消耗战

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

const int MAXN = 25e4 + 10;

inline LL in()

{

    LL x = 0, flag = 1; char ch = getchar();

    while (ch < '0' || ch > '9') { if (ch == '-') flag = 1; ch = getchar(); }

    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();

    return x * flag;

}

int n, m;

struct Gra

{

    int head[MAXN], nume;

    struct Adj { int nex, to; LL w; } adj[MAXN << 1] ;

    void clear()

        {

            memset(head, 0, sizeof head);

            nume = 0;

        }

    void addedge(int from, int to, LL w)

        {

            adj[++ nume] = (Adj) { head[from], to, w } ;

            head[from] = nume ;

        }

    void link(int from, int to, LL w)

        {

            addedge(from, to, w);

            addedge(to, from, w);

        }

} g[2];

int dep[MAXN], up[21][MAXN], lg[MAXN], dfn[MAXN], ind;

LL mn[MAXN];

void DFS(int u, int fa)

{

    dfn[u] = ++ ind;

    dep[u] = dep[fa] + 1;

    up[0][u] = fa;

    for (int i = 1; (1 << i) <= dep[u]; ++ i)

        up[i][u] = up[i - 1][up[i - 1][u]];

    for (int i = g[0].head[u]; i; i = g[0].adj[i].nex)

    {

        int v = g[0].adj[i].to;

        if (v == fa) continue;

        mn[v] = min(mn[u], g[0].adj[i].w);

        DFS(v, u);

    }

}

int lca(int x, int y)

{

    if (dep[x] > dep[y]) swap(x, y);

    while (dep[x] != dep[y]) y = up[lg[dep[y] - dep[x]]][y];

    if (x == y) return x;

    for (int i = lg[dep[x]]; i >= 0; -- i)

        if (up[i][x] != up[i][y]) x = up[i][x], y = up[i][y];

    return up[0][x];

}

int key[MAXN], stk[MAXN], top;

bool iskey[MAXN];

void insert(int u)

{

    if (top == 1) return  (void) (stk[++ top] = u);

    int LCA = lca(u, stk[top]);

    if (LCA == stk[top]) return (void) (stk[++ top] = u);

    while (top > 1 && dep[LCA] <= dep[stk[top - 1]])

    {

        g[1].addedge(stk[top - 1], stk[top], 0);

        -- top;

    }

    if (LCA != stk[top]) g[1].addedge(LCA, stk[top], 0), stk[top] = LCA;

    stk[++ top] = u;

}

LL search(int u)

{

    LL ret = 0;

    for (int i = g[1].head[u]; i; i = g[1].adj[i].nex)

    {

        int v = g[1].adj[i].to;

        ret += search(v);

    }

    if (iskey[u] || ret > mn[u] * 1LL) ret = mn[u];

    iskey[u] = false; g[1].head[u] = 0;

    return ret;

}

bool cmp(int x, int y) { return dfn[x] < dfn[y]; }

int main()

{

    n = in();

    for (int i = 1; i <= n; ++ i) lg[i] = lg[i - 1] + ((2 << lg[i - 1]) == i);

    for (int i = 1; i < n; ++ i)

    {

        int u = in(), v = in(); LL w = in();

        g[0].link(u, v, w);

    }

    mn[1] = 1e18;

    DFS(1, 0);

    m = in();

    while (m --)

    {

        int q = in();

        for (int i = 1; i <= q; ++ i) key[i] = in(), iskey[key[i]] = true ;

        sort(key + 1, key + q + 1, cmp);

        top = 0;

        stk[++ top] = 1;

        for (int i = 1; i <= q; ++ i) insert(key[i]);

        while (top > 1) g[1].addedge(stk[top - 1], stk[top], 0), -- top;

        g[1].nume = 0;

        printf("%lld\n", search(1));

    }

    return 0;

}