做了题,但是 3.24s 加巨大空间太丢人了,能稍稍减小下常数吗,谢谢。时空 O(n+mlogm)。参照了 Fuyuki 的做法。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using ULL = unsigned long long;
#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define fi first
#define se second
bool Mbe;
//template above
const int N = 2.5e5 + 10, M = N * 2;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
int n, m; vector<int> re[N]; vector<PII> e[N];
int ls[M << 5], rs[M << 5], root[M], idx;
LL s[M << 5];
void insert(int l, int r, int v, int &x) {
if (!x) x = ++ idx; s[x] = INF;
if (l == r) return ;
int mid = l + r >> 1;
if (v <= mid) insert(l, mid, v, ls[x]);
if (v > mid) insert(mid + 1, r, v, rs[x]);
}
void upd(int x) { if (ls[x]) s[ls[x]] = min(s[ls[x]], s[x]); if (rs[x]) s[rs[x]] = min(s[rs[x]], s[x]); s[x] = INF; }
int mer(int l, int r, int x, int y) {
if (!x || !y) return x | y;
if (l == r) return s[x] += s[y], x;
int mid = l + r >> 1; upd(x), upd(y);
ls[x] = mer(l, mid, ls[x], ls[y]); rs[x] = mer(mid + 1, r, rs[x], rs[y]);
return x;
}
void dfs(int u, int fa) {
for (int v : re[u]) insert(1, m, v, root[u]);
for (PII _ : e[u]) {
int v = _.fi, w = _.se;
if (v == fa) continue ;
dfs(v, u); s[root[v]] = min(s[root[v]], (LL)w);
root[u] = mer(1, m, root[u], root[v]);
}
}
void print(int l, int r, int x) {
if (l == r) return printf("%lld\n", s[x]), void();
int mid = l + r >> 1; upd(x);
print(l, mid, ls[x]), print(mid + 1, r, rs[x]);
}
void mian() {
scanf("%d", &n);
for (int i = 0, u, v, w; i < n - 1; i ++ ) {
scanf("%d%d%d", &u, &v, &w);
e[u].push_back({v, w}), e[v].push_back({u, w});
}
scanf("%d", &m);
for (int _ = 1; _ <= m; _ ++ ) {
int k, x; scanf("%d", &k);
while (k -- ) { scanf("%d", &x); re[x].push_back(_); }
}
dfs(1, -1); print(1, m, root[1]);
}
bool Med;
int main() {
fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
#ifdef xuyiyang
freopen(".in", "r", stdin); freopen(".out", "w", stdout);
#endif
int T = 1;
while (T -- ) mian();
fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
return 0;
}