题解 P2495 【[SDOI2011]消耗战】

Nemlit

2019-02-22 10:24:38

Solution

[原文地址](https://www.cnblogs.com/bcoier/p/10416804.html) 题意:给定一棵树,割断每一条边都有代价,每次询问会给定一些点,求用最少的代价使所有给定点都和1号节点不连通 ## 暴力$DP$ 我们先考虑暴力怎么做 设$dp[u]$为以$u$为根的子树中,割掉所有给定点的最小代价 转移的时候要分两种情况: 1.若u不是给定点,则$dp[u] = min(u$到根节点的所有边的最小边长,割掉所有含有给定点的子树) $ps:$上述给定子树不一定与u直接相连 2.若u是给定点,显然他必须与1号点分离,所以$dp[u]=u$到根节点的所有边的最小边长 复杂度$O(nm)$,显然对于$m>=1$这种数据是过不了的 下面给出暴力DP代码(吸氧之后有50分): ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define debug printf("Now is Line : %d\n",__LINE__) #define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout) //#define int long long #define inf 1234567890 #define mod 1000000007 il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define maxn 2333//我也不知道问什么数组开大会从RE 50分->TLE 20分 struct edge { int v, w, next; }e[maxn << 1]; int n, m, head[maxn], cnt, is[maxn], dp[maxn]; il void add(int u, int v, int w) { e[++ cnt] = (edge){v, w, head[u]}; head[u] = cnt; } il void dfs(int u, int fr) { int temp = 0; for(re int i = head[u]; i; i = e[i].next) { int v = e[i].v; if(v == fr) continue; if(is[v]) {temp += e[i].w; continue;} dp[v] = min(dp[u], e[i].w); dfs(v, u); temp += dp[v]; } dp[u] = min(dp[u], temp); } int main() { //file(a); n = read(); for(re int i = 1; i < n; ++ i) { int u = read(), v = read(), w = read(); add(u, v, w), add(v, u, w); } int T = read(); while(T --) { memset(is, 0, sizeof(is)); m = read(), dp[1] = inf; for(re int i = 1; i <= m; ++ i) is[read()] = 1; dfs(1, 0); printf("%d\n", dp[1]); } return 0; } ``` 那么剩下五十分我们要怎么得呢? 我们发现$\sum k[i]$是~~非常~~小的,那我们是不是可以在k上做文(luan)章(gao)呢? 我们发现,有很多点在树上我们是没有用到的,所以我们可以考虑重构一棵新的树,这棵树就叫做————虚树 ## 虚树优化$DP$ 虚树的思想是只保留有用的点(在这道题目里面显然是标记点和lca),然后重新构建一棵树,从而使节点大大减少,优化复杂度 那么我们要怎么构建虚树呢? 首先对于每一棵树,我们都可以用dfs序表示出来,所以对于每一次询问,我们把所有的标记点按照dfs序排序,然后压进一个栈中,然后连边即可 ### 具体方法: 我们先对所有标记点按照$dfs$序排序,并依次入栈 我们考虑入栈操作: 假设我们现在要加入的元素为x,第二个元素为y,栈顶为$s$,$l = lca(x, s)$ 因为我们是按$dfs$加入,所以$dfn[s]<dfn[x],dfn[l]<dfn[x]$ 如果l=s,也就是说s是x的祖先,那么s到1号点显然有边需要割掉,所以x对答案并不产生影响,直接忽略 所以x,s肯定在l的两边($dfn[l]<dfn[x]$) 然后我们进行分类讨论 $if(dfn[y] > dfn[l])$ 则说明y在l与x之间,连边$y -> x$,并将x弹出 $if(dfn[y] < dfn[l])$ 则说明l在x与y之间,所以连边$l -> x$,并且令x出栈,l入栈 $if(dfn[y] = dfn[l])$ 则说明y=l,连边 $l -> x$ 建树完成以后,每一个节点都是有用点,即满足暴力DP中的含有给定点的子树,所以每一条边都是可以割掉的,直接转移即可 时间复杂度$O(klogk)$ 代码如下 ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define debug printf("Now is Line : %d\n",__LINE__) #define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout) #define int long long #define inf 123456789000000000 #define mod 1000000007 il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define maxn 250005 struct edge { int v, w, next; }e[maxn << 1]; int n, m, head[maxn], cnt, is[maxn], mi[maxn], dfn[maxn], col, t; int size[maxn], fa[maxn], top[maxn], son[maxn], dep[maxn], s[maxn]; vector<int>v[maxn]; il void add(int u, int v, int w) { e[++ cnt] = (edge){v, w, head[u]}; head[u] = cnt; } il bool cmp(int a, int b){return dfn[a] < dfn[b];} il void dfs1(int u, int fr) { size[u] = 1, fa[u] = fr, dep[u] = dep[fr] + 1; for(re int i = head[u]; i; i = e[i].next) { int v = e[i].v; if(v == fr) continue; mi[v] = min(mi[u], e[i].w); dfs1(v, u), size[u] += size[v]; if(size[son[u]] < size[v]) son[u] = v; } } il void dfs2(int u, int fr) { top[u] = fr, dfn[u] = ++ col; if(!son[u]) return; dfs2(son[u], fr); for(re int i = head[u]; i; i = e[i].next) { int v = e[i].v; if(v != fa[u] && v != son[u]) dfs2(v, v); } } il int lca(int a, int b) { while(top[a] != top[b]) dep[top[a]] > dep[top[b]] ? a = fa[top[a]] : b = fa[top[b]]; return dep[a] < dep[b] ? a : b; } il void push(int x) { if(t == 1) {s[++ t] = x;return;} int l = lca(x, s[t]); if(l == s[t]) return; while(t > 1 && dfn[s[t - 1]] >= dfn[l]) v[s[t - 1]].push_back(s[t]), --t; if(s[t] != l) v[l].push_back(s[t]), s[t] = l; s[++ t] = x; } il int dp(int u) { if(v[u].size() == 0) return mi[u]; int temp = 0; for(re int i = 0; i < v[u].size(); ++ i) temp += dp(v[u][i]); v[u].clear(); return min(mi[u], temp); } signed main() { file(a); n = read(); for(re int i = 1; i < n; ++ i) { int u = read(), v = read(), w = read(); add(u, v, w), add(v, u, w); } mi[1] = inf, dfs1(1, 0), dfs2(1, 1); int T = read(); while(T --) { m = read(); for(re int i = 1; i <= m; ++ i) is[i] = read(); sort(is + 1, is + m + 1, cmp); s[t = 1] = 1; for(re int i = 1; i <= m; ++ i) push(is[i]); while(t > 0) v[s[t - 1]].push_back(s[t]), --t; printf("%lld\n", dp(1)); } return 0; } ```