[洛谷 2495][SDOI2011]消耗战

题目链接

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)\)。

注意到如下两个事实:

  1. 所有询问中关键点的总数与 \(n\) 同阶。
  2. 很多非关键点是没有必要的(比如一个子树内一个关键点都没有,那这个子树内的所有点都不会对答案有贡献)。

我们考虑压缩这棵树,只保留对于 DP 计算有用的节点。

现在要解决两个问题:怎么压缩?哪些节点该保留?

为了确保答案正确,我们压缩时应该确保树的形态不变。具体来说,是祖先-后代的关系不变。

在此前提下,我们要让保留的节点数尽可能少。

毫无悬念,所有的关键点应该保留。同时,为了能确定树的形态(即所有节点间的祖先-后代关系),我们应该保留所有关键点两两之间的最近公共祖先。

下一个问题是,如何建树?

如果直接枚举所有关键点对,计算两两之间的最近公共祖先,时间复杂度显然无法接受。

一种想法是将所有关键点先按 DFS 序排序,按顺序一个一个加到树里。刚开始树上只有 \(1\) 号点。

接下来,我们用一个栈维护在树上一条链上的所有点。这个栈内的所有点满足其 DFS 序单调递增。

我们每次准备将一个关键点加入栈中时,求一下当前栈顶点和要加入的关键点的最近公共祖先 \(p\)。

  1. 如果栈顶就是 \(p\),则可以知道我们加入的关键点和栈中的点在一条链上,直接将关键点加入栈中即可。
  2. 如果栈顶不是 \(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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据