代码开的数组虽然有亿点多,下面是丑陋的代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define Mp make_pair
#define eb emplace_back
#define fir(x, y, z) for(int x = (y); x <= (z); ++ x)
#define fdr(x, y, z) for(int x = (y); x >= (z); -- x)
#define fre(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
namespace io {
const int n = 1e6;
char c, b[n], *i, *j;
inline char gc() {
if (i == j) {
j = (i = b) + fread(b, 1, n, stdin);
if (i == j) return EOF;
} return *i ++;
}
#define gc getchar
template <typename T = int>
inline T read() {
T s = 0; int x = 0;
while (!isdigit(c = gc())) x |= c == '-';
for (; isdigit(c); c = gc())
s = (s << 1) + (s << 3) + (c & 15);
return x ? - s : s;
};
}
using io :: read;
const int N = 500005;
const int inf = 1e9;
typedef int ary[N];
int n, m, tot, cnt, ver[N << 1], nxt[N << 1], val[N << 1], Top, mn[N][19];
ary head, dfn, siz, f, top, dep, son, sta, a, bot, vis, Log, w;
inline void Add_edge(int x, int y, int w) {
ver[++ tot] = y; nxt[tot] = head[x];
val[tot] = w; head[x] = tot;
ver[++ tot] = x; nxt[tot] = head[y];
val[tot] = w; head[y] = tot;
}
inline void Dfs1(int x, int fa) {
siz[x] = 1, f[x] = fa;
dep[x] = dep[fa] + 1;
for (int i = head[x], y; i; i = nxt[i])
if ((y = ver[i]) != fa) {
Dfs1(y, x); siz[x] += siz[y];
if (siz[y] > siz[son[x]]) son[x] = y;
}
}
inline void Dfs2(int x, int fa, int v) {
mn[dfn[x] = ++ cnt][0] = v;
top[x] = x == son[fa] ? top[fa] : x;
bot[x] = x;
if (son[x]) {
int Val;
for (int i = head[x]; i; i = nxt[i])
if (ver[i] == son[x]) {
Val = val[i]; break;
}
Dfs2(son[x], x, Val);
bot[x] = bot[son[x]];
}
for (int i = head[x], y; i; i = nxt[i])
if ((y = ver[i]) != fa && son[x] != y)
Dfs2(y, x, val[i]);
}
inline void Init(int l, int r) {
if (l > r) swap(l, r);
int len = r - l + 1, LOG = 0;
while (1 << LOG + 1 <= len) ++ LOG;
fir (j, 1, LOG) fir (i, l, r - (1 << j) + 1)
mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]);
}
inline int ask(int l, int r) {
if (l > r) swap(l, r);
int log = Log[r - l + 1];
return min(mn[l][log], mn[r - (1 << log) + 1][log]);
}
inline int Lca(int x, int y, int &Min) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
Min = min(Min, ask(dfn[top[x]], dfn[x]));
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
Min = min(Min, ask(dfn[x], dfn[y]));
return x;
}
inline bool cmp(int x, int y) {
return dfn[x] < dfn[y];
}
inline ll Dp(int x, int fa) {
ll sum = 0;
for (int i = head[x], y; i; i = nxt[i])
if ((y = ver[i]) != fa) {
if (vis[y]) sum += val[i];
else sum += min(Dp(y, x), 1ll * val[i]);
}
return sum == 0 ? 1e18 : sum;
}
signed main() {
n = read();
fir (i, 2, n) {
int x = read(), y = read(), w = read();
Add_edge(x, y, w);
}
memset(mn, 0x3f, sizeof mn);
Dfs1(1, 0); Dfs2(1, 0, inf);
fir (i, 1, n) if (!vis[top[i]])
Init(dfn[top[i]], dfn[bot[i]]);
fir (i, 2, n) Log[i] = Log[i >> 1] + 1;
fir (i, 1, n) head[i] = vis[i] = 0;
for (int q = read(); q --;) {
sta[Top = 1] = 1;
head[1] = 0;
m = read();
fir (i, 1, m) a[i] = read();
sort(a + 1, a + m + 1);
m = unique(a + 1, a + m + 1) - a - 1;
sort(a + 1, a + m + 1, cmp);
fir (i, 1, m) vis[a[i]] = 1;
tot = 0;
fir (i, a[1] == 1 ? 2 : 1, m) {
int x, lca = Lca(sta[Top], a[i], x);
if (lca != sta[Top]) {
while (dfn[lca] < dfn[sta[Top - 1]])
Add_edge(sta[Top], sta[-- Top], w[Top + 1]);
if (lca != sta[Top - 1]) {
head[lca] = 0;
w[Top] = inf;
Lca(sta[Top], lca, w[Top]);
Add_edge(lca, sta[Top], w[Top]);
sta[Top] = lca;
w[Top] = inf;
Lca(lca, sta[Top - 1], w[Top]);
} else {
Add_edge(lca, sta[Top], w[Top]);
-- Top;
}
}
head[a[i]] = 0;
sta[++ Top] = a[i];
w[Top] = inf;
Lca(a[i], sta[Top - 1], w[Top]);
}
fir (i, 2, Top) Add_edge(sta[i - 1], sta[i], w[i]);
printf("%lld\n", Dp(1, 0));
fir (i, 1, m) vis[a[i]] = 0;
}
return 0;
}