<虚树+树型DP> SDOI2011消耗战
#include#include #include #include #include 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;}