题解 P2495 【[SDOI2011]消耗战】

· · 题解

一道虚树的练手题。

首先显然有如下做法：

设 f_i 表示以 i 号点为根的子树，i 的子节点中所有关键点均不与 i 号点相连花费的最低成本。则所求答案为 f_1。

对于 i 号点的每个子节点 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;
}