題目大意

給你\(k\)個點，讓這一些點和一號節(jié)點斷開，刪去某一些邊，求最小的刪去邊權之和。

做題的心路歷程

做了\(HG\)昨天的模擬賽，深深感覺到了窩的菜，所以為了\(A\)掉T1這一道毒瘤，窩就來學習一下虛樹。
學到一半，感覺虛樹的原理還是比較簡單的，就是把需要求的點建一棵和原來的樹長得十分相似的一棵樹，然后在這個樹上做\(DP\)。
但是，我寫到完了，就一直T。也不知道為什么。
然后刪掉了所有的memset就瞬間跑了出來。原來是因為自己太慫了。。。

題解

首先如果考慮最簡單的樹形\(DP\)。
\(f[i]\)表示以\(i\)為根節(jié)點的答案。
那么我們需要預處理出每一個節(jié)點到根節(jié)點\(1\)的最小邊權設為\(me[i]\)，那么就得到了\(f[i]=\sum \ min(f[i],me[i])\)
但是發(fā)現(xiàn)，如果每一個詢問都做一遍樹形\(DP\)，那么一定是要炸的。
那么就對于我們需要詢問的節(jié)點建立一個樹，然后在這個樹上跑DP。

代碼

#include <bits/stdc++.h> #pragma GCC optimize(2) #define N 550005 #define ms(a, b) memset(a, b, sizeof(a)) #define ll long long #define BIT 19 using namespace std; template <typename T> void read(T &x) {x = 0; T fl = 1; char ch = 0;for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') fl = -1;for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);x *= fl; } struct edge { int to, nt, w; } E[N << 1]; vector<int> G[N]; int H[N], dfn[N], ispoint[N], f[N][BIT + 5], dep[N], p[N], stk[N]; ll me[N]; int cnt, __dfn, n, Q, k, top; void add_edge(int u, int v, int w) { E[++ cnt] = (edge){v, H[u], w}; H[u] = cnt; } bool cmp(int A, int B) { return dfn[A] < dfn[B]; } void dfs1(int u, int fa) {f[u][0] = fa; dfn[u] = ++ __dfn; dep[u] = dep[fa] + 1; for (int i = 1; i <= BIT; i ++) f[u][i] = f[f[u][i - 1]][i - 1];for (int e = H[u]; e; e = E[e].nt) { int v = E[e].to; if (v == fa) continue; me[v] = E[e].w; if (u != 1 && me[u] < me[v]) me[v] = me[u]; dfs1(v, u); } } int lca(int u, int v) {if (dep[u] < dep[v]) swap(u, v);for (int i = BIT; ~i; i --) if (dep[f[u][i]] >= dep[v]) u = f[u][i]; if (u == v) return u;for (int i = BIT; ~i; i --) if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];return f[u][0]; } void insert(int u) {if (top == 1) { stk[++ top] = u; return; }int Lca = lca(u, stk[top]);if (Lca == stk[top]) { stk[++ top] = u; return; }while (top > 1 && dfn[Lca] <= dfn[stk[top - 1]]) G[stk[top - 1]].push_back(stk[top]), -- top;if (Lca != stk[top]) G[Lca].push_back(stk[top]), stk[top] = Lca; stk[++ top] = u; } ll DP(int u) {ll res = 0;for (int i = 0; i < (int) G[u].size(); i ++) {int v = G[u][i]; res += min(me[v], DP(v));}G[u].clear(); if (ispoint[u]) return me[u]; else return res; } int main() {read(n); for (int i = 1, u, v, w; i < n; i ++) { read(u); read(v); read(w); add_edge(u, v, w); add_edge(v, u, w); }__dfn = 0; dfs1(1, 0);read(Q);while (Q --) {read(k); for (int i = 1; i <= k; i ++) read(p[i]), ispoint[p[i]] = 1; sort(p + 1, p + 1 + k, cmp); top = 0; stk[++ top] = 1; for (int i = 1; i <= k; i ++) insert(p[i]);while (top > 0) { G[stk[top - 1]].push_back(stk[top]); top --; } printf("%lld\n", DP(1));for (int i = 1; i <= k; i ++) G[p[i]].clear(), ispoint[p[i]] = 0; G[0].clear(); }return 0; }

轉載于:https://www.cnblogs.com/chhokmah/p/10695437.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的「洛谷2495」「BZOJ3052」「SDOI2001」消耗战【虚树+树形动态规划】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。