消耗战

题目地址：

https://ac.nowcoder.com/acm/problem/212521

基本思路：

先补充一下数据范围:

,,

我们发现如果没有次的查询单单是询问一次,那么设为切断这颗子树下所有点的最小代价,为到号点的路径中最小的边权,我们可以很容易的得到一个树形的转移方程:

但是我们肯定不能对每次的查询暴力跑,我们观察到,似乎可以从这里入手,因此我们引入虚树的概念。
虚树,实际上就是对于每次查询的点,我们只针对这些有用的点建树,而忽略那些用不到的点,对于虚树的构建我们可以参考下面的步骤:
首先我们要将每次查询的点,根据序进行排序;
然后我们维护一个栈,栈底到栈顶的元素表示虚树中从上到下的一条链,
在这里我们先固定放进根节点,对于每次插入的节点,

当栈中只有一个元素的时候我们直接将插入栈,

否则我们令,

当,那么意味着在栈顶节点的子树中,那么直接将压入栈中,

如果,那么说明和分属的两棵不同的子树，而且所在的子树中已经构建完成了,这时候我们弹栈并且在弹栈过程中连边,直到 或 时停止,这时再判断是否等于:

若不等，先从向连边，然后弹出栈顶，压入，再压入,

否则直接压入。
具体过程大家可以根据代码运行过程,画图理解,我不太会用绘图软件,这里就不引入图片了。

这样我们对于每次查询都构建一棵虚树,然后再在虚树上跑前面的树形过程,那么就能在规定时间里得到答案,虚树的复杂度只与有关为。

参考代码如下,代码中使用树剖求。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define debug(x) cerr << #x << " = " << x << '\n';
#define pll pair <ll, ll>
#define fir first
#define sec second
#define INF 0x3f3f3f3f

namespace IO {
const int SIZE = 1 << 20;
char buf[SIZE], *p1 = buf, *p2 = buf;
char obuf[SIZE], *O = obuf;
int getc() {
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, SIZE, stdin), p1 == p2) ? EOF : *p1++;
}
int read() {
  int x = 0, f = 0;
  char ch = getc();
  while (!isdigit(ch)) f |= ch == '-', ch = getc();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getc();
  return f ? -x : x;
}
template<typename T> void print(T x) {
  if (x < 0) *O++ = '-', x = -x;
  if (x > 9) print(x / 10);
  *O++ = char(x % 10 + '0');
}
template<typename T> void print(T x, char opt) {
  print(x), *O++ = opt;
}
void Flush() {
  fwrite(obuf, O - obuf, 1, stdout);
}
}

using namespace IO;
const int maxn = 5e5 + 10;
struct Edge{
    int to,w,next;
}edge[maxn << 1];
int cnt = 0,head[maxn];
void init() {
  cnt = 0;
  mset(head, -1);
}
void add_edge(int u,int v,int w) {
  edge[++cnt].next = head[u];
  edge[cnt].w = w;
  edge[cnt].to = v;
  head[u] = cnt;
}
int sz[maxn],dep[maxn],son[maxn],fa[maxn];
ll mn[maxn];
int dfn[maxn],top[maxn],tot;
void dfs1(int u,int par,int deep){
  dep[u] = deep; fa[u] = par; sz[u] = 1; son[u] = 0;
  for(int i = head[u] ; i != -1 ; i = edge[i].next){
    int to = edge[i].to;
    if(to == par) continue;
    mn[to] = min(mn[u], (ll)edge[i].w);
    dfs1(to,u,deep + 1);
    sz[u] += sz[to];
    if(sz[to] > sz[son[u]]) son[u] = to;
  }
}
void dfs2(int u,int tp) {
  dfn[u] = ++tot;
  top[u] = tp;
  if (son[u]) dfs2(son[u], tp);
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int to = edge[i].to;
    if (to == fa[u] || to == son[u]) continue;
    dfs2(to, to);
  }
}
int LCA(int x,int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    x = fa[top[x]];
  }
  if (dep[x] < dep[y]) swap(x, y);
  return y;
}
vector<int> G[maxn];
int stk[maxn],tp;
void add(int x,int y){
  G[x].push_back(y);
}
void insert(int x) {
  if (tp == 1) { stk[++tp] = x; return; }
  int lca = LCA(stk[tp], x);
  if (lca == stk[tp]) return;
  while (tp > 1 && dfn[stk[tp - 1]] >= dfn[lca]) add(stk[tp - 1],stk[tp]),tp--;
  if (lca != stk[tp]) add(lca,stk[tp]),stk[tp] = lca;
  stk[++tp] = x;
}
ll calc(int u){
  if(SZ(G[u]) == 0) return mn[u];
  ll res = 0;
  for(auto to : G[u]) res += calc(to);
  G[u].clear();
  return min(mn[u],res);
}
int n,m,k,a[maxn];
inline bool cmp(int x,int y){
  return dfn[x] < dfn[y];
}
signed main() {
  n = read();
  init();
  rep(i,1,n - 1) {
    int u = read(), v = read(), w = read();
    add_edge(u, v, w);
    add_edge(v, u, w);
  }
  mn[1] = (1ll << 60);
  dfs1(1,0,1);
  dfs2(1,1);
  m = read();
  while (m--) {
    k = read();
    rep(i, 1, k) a[i] = read();
    sort(a + 1, a + 1 + k, cmp);
    stk[tp = 1] = 1;
    rep(i, 1, k) insert(a[i]);
    while (tp > 0) add(stk[tp - 1], stk[tp]), tp--;
    print(calc(1),'\n');
  }
  Flush();
  return 0;
}