[BZOJ2286] [Sdoi2011]消耗战

本文主要是介绍[BZOJ2286] [Sdoi2011]消耗战，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=2286

题目大意

给定一棵树，树上有边权，切断一条边消耗边权大小的能量
每次给定一些关键点，使这些关键点都不能与1联通，询问最小代价

题解

树形DP
$dp[i]:使i不与它子树中任意一个关键点联通的最小代价$
$dp[i]=\sum \min\{dp[son[i]],w[i,son[i]]\}_{son[i]不是关键点}/w[i,son[i]]_{son[i]是关键点}$
复杂度$O(NM)$超时
我们发现其实不用每次都对整棵树做一遍$DP$，每次只留下关键点和汇集关键点的点($lca$)即可
(下面的父子关系是省略无关点后的新树)
$dp[i]=\sum \min\{dp[son[i]],w[i,son[i]]\}_{son[i]不是关键点}/w[i,son[i]]_{son[i]是关键点}$
其中$w[i,son[i]]$是原树中两点见的最小边权
可以用ST表预处理出来做到每次$O(logN)$
(这一种抛去无关点建立的新树通常叫做虚树)
如何建立，看下面一段

接下来所说的”树”均指虚树,原来那棵树叫做”原树”.
构建过程如下:
按照原树的dfs序号(记为dfn)递增顺序遍历选择的节点. 每次遍历节点都把这个节点插到树上.
首先虚树一定要有一个根. 随便扯一个不会成为询问点的点作根.
维护一个栈,它表示在我们已经(用之前的那些点)构建完毕的虚树上,以最后一个插入的点为端点的DFS链.
设最后插入的点为p(就是栈顶的点),当前遍历到的点为x.我们想把x插入到我们已经构建的树上去.
求出lca(p,x),记为lca.有两种情况:
　　1.p和x分立在lca的两棵子树下.
　　2.lca是p.
　　(为什么lca不能是x?
　　 因为如果lca是x,说明dfn(lca)=dfn(x)

constmaxn=250000;
varw:array[0..3*maxn,1..3]of longint;dp:array[0..maxn]of int64;pos,dep,t,s,v,p:array[0..maxn]of longint;st:array[0..maxn,0..20]of longint;dis:array[0..maxn,0..20]of int64;i,j,k:longint;n,m,len,a,b,c,tt:longint;
function min(a,b:int64):int64;
begin if a>b then exit(b) else exit(a); end;procedure init(a,b,c:longint);
beginw[len,1]:=b; w[len,2]:=c;if w[a,3]=0 then w[a,3]:=len else w[w[a,1],3]:=len;w[a,1]:=len; inc(len);
end;procedure sort(l,r:longint);
var i,j,a,b:longint;
begini:=l;j:=r;a:=pos[s[(l+r)div 2]];repeatwhile (pos[s[i]]<a) do inc(i);while (pos[s[j]]>a) do dec(j);if not(i>j) then begin b:=s[i]; s[i]:=s[j]; s[j]:=b; inc(i); dec(j); end;until i>j;if l<j then sort(l,j);if i<r then sort(i,r);
end;procedure dfs(a:longint);
var tt:longint;
begintt:=w[a,3]; inc(len); pos[a]:=len;while tt<>0 dobeginif (w[tt,1]<>st[a,0])thenbegindep[w[tt,1]]:=dep[a]+1;st[w[tt,1],0]:=a;dis[w[tt,1],0]:=w[tt,2];dfs(w[tt,1]);end;tt:=w[tt,3];end;
end;procedure prepare;
var i:longint;
beginlen:=0; dep[1]:=1; dfs(1);for i:=1 to 20 dofor j:=1 to n dost[j,i]:=st[st[j,i-1],i-1];for i:=1 to 20 dofor j:=1 to n dodis[j,i]:=min(dis[j,i-1],dis[st[j,i-1],i-1]);
end;function lca(a,b:longint):longint;
var i:longint;
beginif dep[a]<dep[b] then begin i:=a; a:=b; b:=i; end;for i:=20 downto 0 doif dep[st[a,i]]>=dep[b]then a:=st[a,i];if a=b then exit(a);for i:=20 downto 0 doif st[a,i]<>st[b,i]then begin a:=st[a,i]; b:=st[b,i]; end;exit(st[a,0]);
end;function distance(a,b:longint):int64;
var ans:int64; i:longint;
beginif dep[a]<dep[b] then begin i:=a; a:=b; b:=i; end;ans:=maxlongint;for i:=20 downto 0 doif dep[st[a,i]]>=dep[b]then begin ans:=min(ans,dis[a,i]); a:=st[a,i]; end;exit(ans);
end;beginreadln(n); len:=n+1;for i:=1 to n-1 dobeginreadln(a,b,c);init(a,b,c); init(b,a,c);end;prepare;readln(m);for i:=1 to m dobeginread(a);for j:=1 to a dobegin read(s[j]); v[s[j]]:=1; end;sort(1,a);t[1]:=1; t[0]:=1; p[0]:=1; p[1]:=1; len:=n+1;for j:=1 to a dobegintt:=lca(t[t[0]],s[j]);if tt=t[t[0]]then begin inc(t[0]); t[t[0]]:=s[j]; inc(p[0]); p[p[0]]:=s[j]; endelsebeginwhile dep[t[t[0]-1]]>dep[tt] dobeginif v[t[t[0]]]=1then inc(dp[t[t[0]-1]],distance(t[t[0]],t[t[0]-1]))else inc(dp[t[t[0]-1]],min(distance(t[t[0]],t[t[0]-1]),dp[t[t[0]]]));dp[t[t[0]]]:=0; dec(t[0]);end;if v[t[t[0]]]=1then inc(dp[tt],distance(tt,t[t[0]]))else inc(dp[tt],min(distance(tt,t[t[0]]),dp[t[t[0]]]));dp[t[t[0]]]:=0; dec(t[0]);if t[t[0]]<>tt then begin inc(t[0]); t[t[0]]:=tt; inc(p[0]); p[p[0]]:=s[j]; end;inc(t[0]); t[t[0]]:=s[j]; inc(p[0]); p[p[0]]:=s[j];end;end;while t[0]>1 dobeginif v[t[t[0]]]=1then inc(dp[t[t[0]-1]],distance(t[t[0]],t[t[0]-1]))else begin inc(dp[t[t[0]-1]],min(distance(t[t[0]],t[t[0]-1]),dp[t[t[0]]])); dp[t[t[0]]]:=0; end;dec(t[0]);  end;writeln(dp[1]); for j:=1 to p[0] dodp[p[j]]:=0;for j:=1 to a dov[s[j]]:=0;end;
end.

这篇关于[BZOJ2286] [Sdoi2011]消耗战的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---