如题,没找到错误,望大佬帮忙!
#include <iostream>
#include <algorithm>
#include <random>
#include <functional>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <ctime>
// #pragma O(2)
#define int long long
// 返回x的二进制中1的个数
#define ppc(x) __builtin_popcount(x)
// 返回x的二进制中前导0的个数
#define clz(x) __builtin_clz(x)
// 返回x的二进制中后导0的个数
#define ctz(x) __builtin_ctz(x)
// lg(8) = 3, lg(16) = 4, 计算x的以2为底的对数的向下取整, 即x的最高位1的位置
#define lg(x) __lg(x)
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PDI = pair<double, int>;
using PDD = pair<double, double>;
using ULL = unsigned long long;
const int mod = 998244353;
const int N = 3e5 + 10, M = 5e5 + 10;
const int INF = (1LL << 31) - 1;
const LL LLF = 2e18 - 1;
// 用于检测程序占用内存大小
bool Mbe;
// 随机数生成器
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd(1064);
int rd(int l, int r) {return rnd() % (r - l + 1) + l;}
// 取模运算
void addt(int &x, int y) {x += y, x >= mod && (x -= mod);}
void subt(int &x, int y) {x -= y, x < 0 && (x += mod);}
void mult(int &x, int y) {x = (LL)x * y % mod;}
int add(int x, int y) {return x + y >= mod ? x + y - mod : x + y;}
int sub(int x, int y) {return x - y < 0 ? x - y + mod : x - y;}
int mul(int x, int y) {return (LL)x * y % mod;}
// 快速幂
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) mult(res, a);
mult(a, a), b >>= 1;
}
return res;
}
// 最大公约数
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
// 逆元
int inv(int x) {return qpow(x, mod - 2);}
// 二分
int bsearch(int l, int r, function<bool(int)> f) {
while (l < r) {
int mid = (l + r) >> 1;
if (f(mid)) r = mid;
else l = mid + 1;
}
return l;
}
// 读入优化
inline int read() {
int s = 0, w = 1;
char c = getchar();
while (c < 48 || c > 57) {
if (c == '-') w = -1;
c = getchar();
}
while (c >= 48 && c <= 57)
s = (s << 1) + (s << 3) + c - 48, c = getchar();
return s * w;
}
// 输出优化
inline void pf(LL x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) pf(x / 10);
putchar(x % 10 + 48);
}
// 求组合数
// const int Z = 1e6 + 10;
// int fc[Z], ifc[Z];
// int bin(int n, int m) {
// if(n < m) return 0;
// return 1ll * fc[n] * ifc[m] % mod * ifc[n - m] % mod;
// }
// void init_fac(int Z) {
// for(int i = fc[0] = 1; i < Z; i++) fc[i] = 1ll * fc[i - 1] * i % mod;
// ifc[Z - 1] = qpow(fc[Z - 1], mod - 2);
// for(int i = Z - 2; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;
// }
/* template above */
int dfn[N];
int depth[N];
int fa[N][18];
int minv[N];
int lst[N];
int query[N];
int n, q;
int cnt;
int h[N], e[N << 1], ne[N << 1], w[N << 1], idx;
int h0[N], e0[N << 1], ne0[N << 1], idx0;
int f[N];
int st[N];
void addEdge(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
void addEdge(int a, int b) {
e0[idx0] = b, ne0[idx0] = h0[a], h0[a] = idx0 ++;
}
void dfs(int u, int dep) {
dfn[u] = ++cnt;
depth[u] = dep;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (dfn[j]) continue;
minv[j] = min(minv[u], w[i]);
dfs(j, dep + 1);
fa[j][0] = u;
for (int k = 1; k <= 17; k ++) {
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int k = 17; k >= 0; k --) {
if (depth[fa[a][k]] >= depth[b]) {
a = fa[a][k];
}
}
if (a == b) return a;
for (int k = 17; k >= 0; k --) {
if (fa[a][k] != fa[b][k]) {
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}
void dfs0(int u) {
int sum = 0;
for (int i = h0[u]; ~i; i = ne0[i]) {
int j = e0[i];
dfs0(j);
sum += f[j];
}
if (query[u]) {
f[u] = minv[u];
}
else {
f[u] = min(minv[u], sum);
}
// 清空虚树
query[u] = 0;
h0[u] = -1;
}
void solve() {
minv[1] = LLF;
cin >> n;
memset(h, -1, sizeof h);
memset(h0, -1, sizeof h0);
for (int i = 1; i <= n - 1; i ++) {
int x, y, z;
cin >> x >> y >> z;
addEdge(x, y, z), addEdge(y, x, z);
}
dfs(1, 1);
// for (int i = 1; i <= n; i ++) {
// cout << minv[i] << ' ';
// }
// cout << endl;
cin >> q;
while (q --) {
int k;
cin >> k;
for (int i = 1; i <= k; i ++) {
cin >> lst[i];
query[lst[i]] = 1;
}
sort(lst + 1, lst + 1 + k, [](int a, int b) {
return dfn[a] < dfn[b];
});
int tt = 0;
st[++tt] = lst[1];
for (int i = 2; i <= k; i ++) {
int now = lst[i];
int lc = lca(now, st[tt]);
while (1) {
if (depth[lc] >= depth[st[tt - 1]]) {
if (lc != st[tt]) {
addEdge(lc, st[tt]);
if (lc != st[tt - 1]) {
st[tt] = lc;
}
else {
tt --;
}
}
break;
}
else {
addEdge(st[tt - 1], st[tt]);
tt --;
}
}
st[++tt] = now;
}
while (--tt) {
addEdge(st[tt], st[tt + 1]);
}
dfs0(st[1]);
// cout << st[1] << endl;
// for (int i = 1; i <= k; i ++) {
// cout << f[lst[i]] << ' ';
// }
// cout << endl;
cout << f[st[1]] << endl;
idx0 = 0;
}
}
bool Med;
signed main() {
fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0);
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
while (T --) solve();
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}