目录
显示
题目链接
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; }