洛谷 P2495 [SDOI2011]消耗战 题解

题目链接

题目描述：

给你一个有边权的树，若干次询问，每次询问包含一个不含点 $1$的 $k$个点的点集，求点 $1$与这些点都不连通的最小代价（删除一些边，代价是他们的权值和）。

解题思路：

首先考虑如果只有一次询问可以怎么做，不难发现转换为点 $1$为根的树后 $DP可以实现$,设 $mincast(i)$为根到点 $i$路径上的最小边权, $dp(i)$为切断以 $i$为根的子树上所有给出的点的最小代价。那么对于点 $i$，
1、如果它是给出的点，那么 $dp(i)$就是 $mincast(i)$（因为这个点必须去除）
2、如果这个点不是给出的点，那么 $dp(i)=min(mincast(i),∑dp(k))$其中 $k$是 $i$的儿子节点。

但是这个题有多次询问，每次询问都进行一次复杂度 $O(n)的dp$显然会超时，发现 $∑k$范围不大，可以从这里入手，当然也是看了别人的题解才知道虚树，也通过这题学习了下虚树。

每次询问建立一课虚树，虚树是只保留原来树上所需要的点新建的一棵树，观察发现我们其实只需要保留给出的点及其它们的 $lca$，如图所示，如果红色的点为给出的点：

那么保留有用的点后的树应该是这样的：

那么有 $k$个点，两两产生 $lca$会有 $k*k$个点么，答案是不会的，如果对于当前给出的点 $g$它与之前给出的两个点 $i,j$产生了两个不同的 $lca$记坐 $lca_{ig},lca_{jg}$，并记之前已经产生的 $i和j$的 $lca为lca_{ij}$，那么一定有 $lca_{ij}=lca_{ig}$或 $lca_{ij}=lca_{jg}$（可以画图，然后自己想下）,也就是说每次最多产生一个新的 $lca$，那么虚树上的点不会超过 $k*2$个。接下来我们只要能在不访问其它点的情况下把这个虚树建起来就OK了。

如何建立呢，我们先预处理出原树上每个点的dfs序，记作 $fdsn(i)$，然后对于每次询问，将询问的 $k$个点按dfs序排序，接着用一个栈来维护根到栈顶元素的链（这样可以保证一个点的子孙节点肯定不会比它早入栈，从而保证了链的正确性），首先当然是点 $1$入栈，接下来一次访问已排序了的 $k$个点：
1、如果当前元素 $a_i$和栈顶元素 $s[top]$的 $lca= s[top]$，这时 $top$是 $a[i]$的祖先节点，那么直接将当前元素入栈。

2、如果当前元素 $a_i$和栈顶元素 $s[top]$的 $lca不等于s[top]$，那么我们要考虑 $s[top-1]$和 $lca$的关系：
1）如果 $dfsn[s[top-1]]<dfsn[lca]$,那么就说明这个 $lca$是介于 $s[top-1]$和 $s[top]$之间的，那么我们将 $s[top]$出栈，将 $lca$和 $a[i]$入栈,并连边 $lca->s[top]$(再不连就没机会啦)。

2）如果 $dfsn[s[top-1]]=dfsn[lca]$，我们只需将 $top$出栈，将 $a[i]$入栈，并连边 $lca->s[top]$(再不连就没机会啦)。

3)如果 $dfsn[s[top-1]]>dfsn[lca]$,我们不断 $pop$，知道符合1)或者2)。

最后将栈中的点全部不连边，这样我们的虚树就建立完成了，是可以通过的，不过根据这题题意这个虚树还能再一点小优化，就是如果当前点是给出的 $k$个点中的一个，那么它的子孙全部不必入栈，因为这个点就必须断开了（就是说虚树有且只有根节点是给出的结点）：

对于上图我们的虚数只要这样就可以了:

这个优化怎么做呢，因为新的 $lca$不会是给出的点，那么对于之前的1、如果当前元素 $a_i$和栈顶元素 $s[top]$的 $lca= top$，这时 $top$是 $a[i]$的祖先节点，那么直接将当前元素入栈。
我们在入栈前判断下这个 $top$是不是给出的点即可，如果是那么当前元素不必入栈。

最后我们只需要树上DP即可。

其它：
1、虚树可以不必连双向边，因为根节点固定是 $1$。
2、虽然每条边权值不会爆 $int$，但是加起来会。
3、对于虚树的边清空可以在DP时顺便做了。
4、LCA求法这里没讲，可以百度。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5; 
const long long inf=1e18;
struct node{int to,cast;node(int to,int cast):to(to),cast(cast){}
};
int lv[maxn],fa[maxn],son[maxn],size[maxn],top[maxn];//求lca所需变量 
int n,a[maxn],dfsn[maxn],cnt,vis[maxn],st[maxn];
//    k个数，dfs序，dfs的，是否是给出的点 ，栈  
vector<node>v[maxn];//原边 
vector<int> xv[maxn];//虚树的边 
long long mincast[maxn];
long long dp(int x)
{if(vis[x])return mincast[x];long long ans=0;for(int i=0;i<xv[x].size();i++)ans+=dp(xv[x][i]);xv[x].clear();return min((long long)mincast[x],ans);
}
void dfs(int x,int f,int deep)
{dfsn[x]=cnt++;fa[x]=f;lv[x]=deep;size[x]=1;for(int i=0;i<v[x].size();i++)if(v[x][i].to!=f){int to=v[x][i].to;mincast[to]=min((long long)v[x][i].cast,mincast[x]);dfs(to,x,deep+1);size[x]+=size[to];if(size[son[x]]<size[to])son[x]=to;}	
}
void dfs2(int x,int p)
{top[x]=p;if(son[x])dfs2(son[x],p);for(int i=0;i<v[x].size();i++){int to=v[x][i].to;if(lv[to]>lv[x]&&to!=son[x])dfs2(to,to);		}}
int lca(int x,int y)
{	while(top[x]!=top[y]){if(lv[top[x]]<lv[top[y]])swap(x,y);x=fa[top[x]];}return lv[x]>lv[y]?y:x;
}
int cmp(int x,int y){return dfsn[x]<dfsn[y]; 
} 
void addedge(int x,int y,int z)
{v[x].push_back(node(y,z));v[y].push_back(node(x,z)); 
}
int main(){int n;cin>>n;for(int i=1;i<n;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);addedge(x,y,z);mincast[i]=inf;} cnt=1;dfs(1,-1,0);dfs2(1,1);int q;cin>>q;while(q--){int k,x=-1;scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&a[i]);vis[a[i]]=1;}sort(a,a+k,cmp);int index=0;st[0]=1;for(int i=0;i<k;i++){int tp=st[index];int lca_=lca(tp,a[i]);if(lca_==tp){if(!vis[tp])st[++index]=a[i];}else{while(dfsn[st[index-1]]>dfsn[lca_]){xv[st[index-1]].push_back(st[index]);index--;}		tp=st[index];if(dfsn[st[index-1]]<dfsn[lca_]){xv[lca_].push_back(tp);st[index]=lca_;st[++index]=a[i];}else if(dfsn[st[index-1]]==dfsn[lca_]){xv[lca_].push_back(tp);st[index]=a[i];}				}}while(index){xv[st[index-1]].push_back(st[index]);index--;}/*输出看看虚树有没有建错 for(int i=1;i<=n;i++){if(xv[i].size()==0)continue;cout<<i<<" :"<<endl;for(int j=0;j<xv[i].size();j++)cout<<xv[i][j]<<' ';cout<<endl;xv[i].clear();}*/cout<<dp(1)<<endl;for(int i=0;i<k;i++)vis[a[i]]=0;}return 0;
}