引入
例题：[BZOJ-2286]消耗战
在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。
考虑到每次资源重新分布后只需要断开K个岛屿的连通性，所以树上有很多点是没有用的。如果可以从原树中抽出一部分节点，保持原有的父子关系，使得这些点仅仅包含被选中的k个节点和一部分他们的LCA，节点间的边权为他们在原树上的距离，那么问题就能得到简化。
关键问题是如何将对答案有影响的点抽出来并且重构成一棵树。此时引入虚树的概念。顾名思义，虚树是从原树中抽象出来的一棵树。
虚树构造
首先引入单调栈的概念，单调栈维护的是原树中的一条链，栈中每一个节点的父亲(广义)为其相邻的前一个节点。构造的具体步骤如下：
1.将根入栈
2.按照DFS序从小到大对待处理的节点依次判断，若该节点与栈首的LCA就是栈首，那么说明这个节点仍然在维护的链上，直接入栈即可。
3.若LCA不是栈首，那么开始弹栈，直到栈首节点后一个节点的DFS序小于等于LCA的DFS序则停止。若LCA就是栈首后一个节点，则将栈首与LCA连边，弹栈；否则再将LCA入栈。
4.让待处理节点入栈
5.最后所有节点入栈后，对栈内的节点进行连边。虚树到此构造完毕。
模板
注：来自于题目[BZOJ-2286]
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#define N 300010
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i,k,lsum=1,cnt,L,Lsum=1,x,y,c;
int head[N],id[N],f[N][22],a[N],v[N],d[N],p[30],Head[N],b[N],z[N],cost[N][22],df[N];
LL dp[N];
vector <int> son[N];
struct Edge{
int t,next,d;
}e[N*4],E[N*4];
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline LL Min(LL a,LL b){return (a<b)?a:b;}
inline bool cmp(int a,int b){return (id[a]<id[b]);}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Add(int &s,int &t,int &l){
e[lsum].t=t; e[lsum].next=head[s]; e[lsum].d=l; head[s]=lsum++;
e[lsum].t=s; e[lsum].next=head[t]; e[lsum].d=l; head[t]=lsum++;
}
inline void Maketree(int x){
int i=0,t=0;
v[x]=1;
for (i=head[x];i;i=e[i].next){
t=e[i].t;
if (v[t]) continue;
son[x].push_back(t); f[t][0]=x;
d[t]=d[x]+1; cost[t][0]=e[i].d;
Maketree(t);
}
}
inline void Dfs(int x){
int i=0,s=0;
id[x]=++cnt;
for (i=1;i<=21;i++){
f[x][i]=f[f[x][i-1]][i-1];
cost[x][i]=Min(cost[x][i-1],cost[f[x][i-1]][i-1]);
}
if (!son[x].size()) return;
for (s=son[x].size(),i=0;i<s;i++) Dfs(son[x][i]);
}
inline void Ready(){
for (i=1,p[0]=1;i<=21;i++) p[i]=p[i-1]*2;
d[1]=1; Maketree(1); Dfs(1);
}
inline int LCA(int x,int y){
int l=0,i=0; L=INF;
if (d[x]<d[y]) Swap(x,y);
l=d[x]-d[y];
for (i=0;i<=21;i++)
if (l&p[i]) L=Min(L,cost[x][i]),x=f[x][i];
if (x==y) return x;
for (i=21;i>=0;i--)
if (f[x][i]!=f[y][i]) L=Min(L,cost[x][i]),x=f[x][i],y=f[y][i];
return f[x][0];
}
inline void ADD(int x,int y){
LCA(x,y);
E[Lsum].t=y; df[y]=L; E[Lsum].next=Head[x]; Head[x]=Lsum++;
}
inline void DP(int x){
int i=0,r=0;
dp[x]=0;
if (!Head[x]) return;
for (i=Head[x];i;i=E[i].next){
r=E[i].t; DP(r);
(b[r]!=(n+m))?dp[x]+=Min(dp[r],df[r]):dp[x]+=df[r];
}
}
inline void Work(){
int i=0,p=0;
sort(a+1,a+1+k,cmp);
Lsum=z[z[0]=1]=1; Head[1]=0;
for (i=1;i<=k;i++){
p=LCA(a[i],z[z[0]]);
if (p!=z[z[0]]){
while (id[z[z[0]-1]]>id[p]) ADD(z[z[0]-1],z[z[0]]),z[0]--;
if (p!=z[z[0]-1]) Head[p]=0,ADD(p,z[z[0]]),z[z[0]]=p;
else ADD(p,z[z[0]--]);
}
Head[a[i]]=0; z[++z[0]]=a[i];
}
for (i=1;i<z[0];i++) ADD(z[i],z[i+1]);
DP(1); printf("%lld\n",dp[1]);
}
int main(){
n=read();
for (i=1;i<n;i++){
x=read(); y=read(); c=read();
Add(x,y,c);
}
Ready(); m=read();
while (m--){
k=read();
for (i=1;i<=k;i++) a[i]=read(),b[a[i]]=n+m;
Work();
}
return 0;
}
相关例题
[HEOI2014] 大工程
题目描述
国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在两个国家a,b之间建一条新通道需要的代价为树上a,b的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了k个点，然后在它们两两之间 新建
C_{k}^{2}
条新通道。现在对于每个计划，我们想知道：
- 这些新通道的代价和
- 这些新通道中代价最小的是多少
- 这些新通道中代价最大的是多少
解法
从原树中抽出被选中的节点构造虚树，然后统计每个节点对应子树下有多少被选中的节点，通过计算边权的贡献算总距离，然后DP计算最大和最小代价。
代码
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#define N 1000010
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i,x,y,k,lsum=1,mians,L,q,top,mxans,cnt;
int dp[N][3],f[N][25];
LL Ans;
LL size[N];
int a[N],b[N],v[N],head[N],id[N],d[N],p[25],z[N];
vector <int> s[N],S[N];
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline bool cmp(const int a,const int b){return (id[a]<id[b]);}
struct Edge{
int t,next,d;
}e[N*4];
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Maketree(int x){
int i=0,t=s[x].size(),w=0;
if (v[x]) return;
v[x]=1; id[x]=++id[0];
for (i=0;i<t;i++){
w=s[x][i];
if (!v[w]){
S[x].push_back(w); d[w]=d[x]+1;
f[w][0]=x; Maketree(w);
}
}
}
inline void Dfs(int x){
int i=0,t=S[x].size(),w=0;
for (i=1;i<=20;i++){
f[x][i]=f[f[x][i-1]][i-1];
}
for (i=0;i<t;i++) Dfs(S[x][i]);
}
inline void Ready(){
int i=0;
for (i=0;i<=20;i++) p[i]=1<<i;
d[1]=1; Maketree(1); Dfs(1);
id[0]=z[0]=0;
}
inline int LCA(int x,int y){
int i=0,l=0;
if (d[x]<d[y]) Swap(x,y);
l=d[x]-d[y]; L=0;
for (i=0;i<=20;i++)
if (l&p[i]) L+=p[i],x=f[x][i];
if (x==y) return x;
for (i=20;i>=0;i--)
if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
inline void Add(int s,int t){
LCA(s,t);
e[lsum].t=s; e[lsum].d=L; e[lsum].next=head[t]; head[t]=lsum++;
}
inline void Update(int x){
int i=0,t=0;
size[x]=0;
if (b[x]==n+q) size[x]=1,cnt++;
for (i=head[x];i;i=e[i].next){
t=e[i].t; Update(t); size[x]+=size[t];
}
}
inline void Dp(int x){
int i=0,t=0;
LL l=0;
if (b[x]==n+q) dp[x][0]=dp[x][1]=0;
else dp[x][0]=-INF,dp[x][1]=INF;
for (i=head[x];i;i=e[i].next){
t=e[i].t; Dp(t); l=e[i].d;
Ans+=(LL)l*((LL)cnt-size[t])*(LL)size[t];
mxans=Max(mxans,dp[x][0]+l+dp[t][0]);
mians=Min(mians,dp[x][1]+l+dp[t][1]);
dp[x][0]=Max(dp[x][0],dp[t][0]+l);
dp[x][1]=Min(dp[x][1],dp[t][1]+l);
}
}
inline void Work(){
int i=0,p=0;
sort(a+1,a+1+k,cmp);
z[top=1]=1; lsum=1; head[1]=0;
for (i=1;i<=k;i++){
if (a[i]==1) continue;
p=LCA(a[i],z[top]);
if (p!=z[top]){
while (id[p]<id[z[top-1]]) Add(z[top],z[top-1]),top--;
if (p!=z[top-1]) head[p]=0,Add(z[top],p),z[top]=p;
else Add(z[top--],p);
}
z[++top]=a[i]; head[a[i]]=0;
}
for (i=1;i<top;i++) Add(z[i+1],z[i]);
cnt=0; Ans=0; mians=INF; mxans=-INF;
Update(1); Dp(1);
printf("%lld %d %d\n",Ans,mians,mxans);
}
int main(){
n=read();
for (i=1;i<n;i++){
x=read(); y=read();
s[x].push_back(y); s[y].push_back(x);
}
Ready(); q=read();
while (q--){
k=read();
for (i=1;i<=k;i++) a[i]=read(),b[a[i]]=n+q;
Work();
}
return 0;
}
