[SDOI2011]消耗戰

題意：

給出n個點的一棵帶有邊權的樹,以及q個詢問.每次詢問給出k個點,詢問這使得這k個點與1點不連通所需切斷的邊的邊權和最小是多少.

題解：

樹型dp+虛樹
dp[x]:切斷x及其子樹上詢問點的最小代價
預處理出minv[pos]代表從11到pos路徑上最小的邊權
如果pos是詢問點,dp(pos)=minv[pos]
否則，最小代價dp(pos)=min(minv[pos],∑dp(to))（其中to是pos的兒子）
如果pos為詢問點，按理說不用dp[to]的值，但是仍然要對其兒子進行dfs，因為清空虛樹需要對整個虛樹進行遍歷
如果對整個子樹進行dp，復雜度過高，這時候就需要建虛樹，（關于虛樹見博文）
建虛圖：

void insert(int x) {if(top == 1) {s[++top] = x; return ;}int lca = LCA(x, s[top]);if(lca == s[top]) return ;//以為s[top]也是關鍵點，那么s[top]子樹里的點就沒必要處理了 while(top > 1 && dfn[s[top - 1]] >= dfn[lca]) add_edge(s[top - 1], s[top]), top--;if(lca != s[top]) add_edge(lca, s[top]), s[top] = lca;//s[++top] = x; }

為什么(lca == s[top]直接推出不把x加棧內
因為s[top]也是關鍵點，x也是關鍵點，x是s[top]的子樹，那根據題意如果將s[top]與根節點斷開，x節點自然也就斷開了，也就是我們只需要考慮s[top]即可（x自動被考慮其中）

代碼：

// luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) #define LL long long char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf; using namespace std; const int MAXN = 250001; inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f; } char obuf[1 << 24], *O=obuf; void print(LL x) {if(x > 9) print(x / 10);*O++= x % 10 + '0'; } int N, M; struct Edge {int u, v, w, nxt; }E[MAXN << 1]; int head[MAXN], num = 1; inline void AddEdge(int x, int y, int z) {E[num] = (Edge) {x, y, z, head[x]};head[x] = num++; } vector<int> v[MAXN]; void add_edge(int x, int y) {v[x].push_back(y); } int a[MAXN], dfn[MAXN], topf[MAXN], siz[MAXN], son[MAXN], s[MAXN], top, deep[MAXN], fa[MAXN], ID = 0; LL mn[MAXN]; void dfs1(int x, int _fa) {siz[x] = 1; fa[x] = _fa;for(int i = head[x]; i != -1; i = E[i].nxt) {if(E[i].v == _fa) continue;deep[E[i].v] = deep[x] + 1;mn[E[i].v] = min(mn[x], (LL)E[i].w);dfs1(E[i].v, x);siz[x] += siz[E[i].v];if(siz[E[i].v] > siz[son[x]]) son[x] = E[i].v;} } void dfs2(int x, int topfa) {topf[x] = topfa;dfn[x] = ++ID;if(!son[x]) return ;dfs2(son[x], topfa);for(int i = head[x]; i != -1; i = E[i].nxt) if(!topf[E[i].v]) dfs2(E[i].v, E[i].v); } int LCA(int x, int y) {while(topf[x] != topf[y]) {if(deep[topf[x]] < deep[topf[y]]) swap(x, y);x = fa[topf[x]];}if(deep[x] < deep[y]) swap(x, y);return y; } void insert(int x) {if(top == 1) {s[++top] = x; return ;}int lca = LCA(x, s[top]);if(lca == s[top]) return ;//以為s[top]也是關鍵點，那么s[top]子樹里的點就沒必要處理了 while(top > 1 && dfn[s[top - 1]] >= dfn[lca]) add_edge(s[top - 1], s[top]), top--;if(lca != s[top]) add_edge(lca, s[top]), s[top] = lca;//s[++top] = x; } LL DP(int x) {if(v[x].size() == 0) return mn[x];LL sum = 0;for(int i = 0; i < v[x].size(); i++) sum += DP(v[x][i]);v[x].clear();return min(sum, (LL)mn[x]); } int comp(const int &a, const int &b) {return dfn[a] < dfn[b]; } int main() {memset(head, -1, sizeof(head));//memset(mn, 0xff, sizeof(mn));mn[1] = 1ll << 60;N = read();for(int i = 1; i <= N - 1; i++) {int x = read(), y = read(), z = read();AddEdge(x, y, z); AddEdge(y, x, z);}deep[1] = 1;dfs1(1, 0);dfs2(1, 1);M = read();/*for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++)printf("%d %d %d\n", i, j, LCA(i, j));*///for(int i = 1; i <= N; i++) printf("%d ", mn[i]); puts("");while(M--) {int K = read();for(int i = 1; i <= K; i++) a[i] = read();sort(a + 1, a + K + 1, comp);s[top = 1] = 1;for(int i = 1; i <= K; i++) insert(a[i]);while(top > 0) add_edge(s[top - 1], s[top]), top--;print(DP(1)), *O++ = '\n'; }fwrite(obuf, O-obuf, 1 , stdout); return 0; }

總結

以上是生活随笔為你收集整理的[SDOI2011]消耗战的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。