目录
显示
题目链接
https://www.luogu.com.cn/problem/P2495
题解
一道虚树的练手题。
首先显然有如下做法：
设 \(f_i\) 表示以 \(i\) 号点为根的子树，\(i\) 的子节点中所有关键点均不与 \(i\) 号点相连花费的最低成本。则所求答案为 \(f_1\)。
对于 \(i\) 号点的每个子节点 \(son\)，有两种情况：
- 当前子节点 \(son\) 是关键点，则连接 \(i\) 与 \(son\) 的边一定要切断。\(f_i=f_i+w(i,son)\)。
- 当前子节点 \(son\) 不是关键点，则可以选择切断以 \(son\) 为根的子树内所有关键点与 \(son\) 的联系，或者直接切断连接 \(i\) 和 \(son\) 的边。\(f_i=f_i+\min(w(i,son),f_{son})\)。
一次询问的时间复杂度为 \(O(n)\)，总时间复杂度为 \(O(nq)\)。
注意到如下两个事实：
- 所有询问中关键点的总数与 \(n\) 同阶。
- 很多非关键点是没有必要的（比如一个子树内一个关键点都没有，那这个子树内的所有点都不会对答案有贡献）。
我们考虑压缩这棵树，只保留对于 DP 计算有用的节点。
现在要解决两个问题：怎么压缩？哪些节点该保留？
为了确保答案正确，我们压缩时应该确保树的形态不变。具体来说，是祖先-后代的关系不变。
在此前提下，我们要让保留的节点数尽可能少。
毫无悬念，所有的关键点应该保留。同时，为了能确定树的形态（即所有节点间的祖先-后代关系），我们应该保留所有关键点两两之间的最近公共祖先。
下一个问题是，如何建树？
如果直接枚举所有关键点对，计算两两之间的最近公共祖先，时间复杂度显然无法接受。
一种想法是将所有关键点先按 DFS 序排序，按顺序一个一个加到树里。刚开始树上只有 \(1\) 号点。
接下来，我们用一个栈维护在树上一条链上的所有点。这个栈内的所有点满足其 DFS 序单调递增。
我们每次准备将一个关键点加入栈中时，求一下当前栈顶点和要加入的关键点的最近公共祖先 \(p\)。
- 如果栈顶就是 \(p\)，则可以知道我们加入的关键点和栈中的点在一条链上，直接将关键点加入栈中即可。
- 如果栈顶不是 \(p\)，则需要将栈中的一些点弹出来，使得新加入的点和栈里的点在一条链上。具体来说，我们需要不停地将栈顶弹出，直到要插入的点的 DFS 序小于栈顶下面的点的 DFS 序。接下来分两种情况：
- 如果此时栈顶是 \(p\)，直接将关键点插入栈；
- 如果此时栈顶不是 \(p\)（显然这时候 \(p\) 的 DFS 序比栈顶大），说明 \(p\) 不在链上，将栈顶弹出，插入 \(p\) 和关键点。
弹栈的时候顺带把边连接一下，树就建好啦。在新的树上跑原来的 DP 就可以了。
经过这样的操作，我们各次建树时的节点数之和将会控制在 \(O(n)\) 的级别，可以通过本题。
// Problem : P2495 [SDOI2011]消耗战
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/P2495
// Memory Limit : 500 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
struct graph
{
struct edge
{
int v,w,next;
}e[1000005];
int head[500005],ch,cnt;
void addedge(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
}t1,t2;
int fa[500005][25],mind[500005][25],dis[500005],dep[500005],dfn[500005],cnt;
int a[500005];
long long f[500005];
int sta[500005];
int d;
set<int> s;
bool cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
void dfs1(int u,int f)
{
dfn[u]=++cnt;
dep[u]=dep[f]+1;
fa[u][0]=f;
for(int i=1;i<=20;i++)
{
fa[u][i]=fa[fa[u][i-1]][i-1];
mind[u][i]=min(mind[u][i-1],mind[fa[u][i-1]][i-1]);
}
for(int i=t1.head[u];i;i=t1.e[i].next)
{
int v=t1.e[i].v,w=t1.e[i].w;
if(v!=f)
{
dis[v]=dis[u]+w;
mind[v][0]=w;
dfs1(v,u);
}
}
}
void dfs2(int u)
{
f[u]=0;
for(int i=t2.head[u];i;i=t2.e[i].next)
{
int v=t2.e[i].v,w=t2.e[i].w;
dfs2(v);
if(s.count(v))f[u]+=w;
else f[u]+=min(f[v],1ll*w);
}
return;
}
int getlca(int x,int y)
{
d=1<<30;
if(dep[x]>dep[y])swap(x,y);
for(int i=20;i>=0;i--)
if(dep[y]-(1<<i)>=dep[x])
{
d=min(d,mind[y][i]);
y=fa[y][i];
}
if(x==y)return x;
for(int i=20;i>=0;i--)
if(fa[x][i]!=fa[y][i])
{
d=min(d,min(mind[x][i],mind[y][i]));
x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int u,v,w;
cin>>u>>v>>w;
t1.addedge(u,v,w);
t1.addedge(v,u,w);
}
dfs1(1,1);
int q;
cin>>q;
while(q--)
{
s.clear();
int k;
cin>>k;
for(int i=1;i<=k;i++)
{
cin>>a[i];
s.insert(a[i]);
}
sort(a+1,a+k+1,cmp);
sta[1]=1;
int top=1;
t2.head[1]=0;
for(int i=1;i<=k;i++)
{
int lca=getlca(a[i],sta[top]);
if(lca!=sta[top])//新加的点和原来在栈里的点不在一条链上
{
while(dfn[lca]<dfn[sta[top-1]])
{
int u=sta[top-1],v=sta[top];
getlca(u,v);
t2.addedge(u,v,d);
top--;
}
if(dfn[lca]>dfn[sta[top-1]])//lca 未入栈
{
getlca(lca,sta[top]);
t2.head[lca]=0;
t2.addedge(lca,sta[top],d);
top--;
sta[++top]=lca;
}
else
{
int u=sta[top-1],v=sta[top];
getlca(u,v);
t2.addedge(u,v,d);
top--;
}
}
t2.head[a[i]]=0;
sta[++top]=a[i];
}
while(top>1)//最后记得把栈里的点也连上边
{
int u=sta[top-1],v=sta[top];
getlca(u,v);
t2.addedge(u,v,d);
top--;
}
dfs2(1);
cout<<f[1]<<endl;
}
return 0;
}