题解 P2495 【[SDOI2011]消耗战】
shadowice1984 · · 题解
虚树
作为虚树的经典例题，拿这道题介绍一下虚树是什么好了~
dfs原理
不知道大家发现一件事了没有，我们关于"树"的所有信息，绝大部分是通过dfs处理出来的，但是我们发现一件事，dfs其实在底层实现上，并不是大家脑海中想象的dfs。
当你的程序编译出来之后，你觉得你在跑dfs，但是计算机并不这么想，因为你甚至没有建树，实际上只有邻接表而已，树？不存在的，而你以为你在这个树上进行了所谓的"深度优先搜索"，而计算机并不这么认为，它只是按一定的指令对一个栈进行了反复的push和pop，期间做一些事罢了(应该都知道递归函数的实现过程隐性的开了一个栈吧……)
水了这么多，其实只是想说两件事，第一，我们做dfs可以了解树的信息，而且了解的很充分，第二，我们可以在不建树的情况下做dfs，只要我们掌握了可以模拟dfs的信息即可，也就是说，在跑dfs的过程中，我们究竟对开出来的栈进行了什么操作
虚树的构建
emm大家应该都知道这道题是个树形dp吧。首先让我们先来写个暴力
令sum[i]表示切断i的子树中所有询问点的最小代价之和，并且你不能直接切掉i，再令mi[i]表示i到1号点的路径中最小的边权，那么我们可以得到这样一个转移方程
sum[i]=sigma(min(mi[v],sum[v]) (v∈i.son)
意义就是我们枚举i的所有子树，为了切断这个子树v，要不然就直接断了v，一了百了，或者可以切断v中的所有询问点。答案就是sum[1]
然后我们可以简单粗暴的跑一边dfs，dp得出答案，复杂度O(N^2)，40pts get√
但是呢，我们发现更新i仅和v有关，跟i一点关系没有……，这意味这我们可以跳过若干个无用的节点，将一个直路径压缩为一条边(这里指一个点到自己的直系祖先的路径)。但是如何区别有用和没用的节点呢？显然所有询问点全部有用，1号点也有用，但是光这些是不行的，可能不存在祖先关系，因此还要加一些别的点
然后诸位dalao经过研究发现，如果我们把询问点按dfs序排序，相邻的点求一个lca，询问点+这些lca就可以保证对于任意一个集合中的点，存在且仅有一条仅包含两个集合点的直路径，(1号点除外)
那么我们可以把这种关系认为是父子关系，举个栗子
图中的红点是询问点，绿点是lca，蓝色的路径表示边，于是我们就从黑树中抽出了一只树同时保留了关于红点的全部信息
也就是说，对于这道题，我们可以建出这样的树，然后再这种树上跑dfs，就可以达到同样的树形dp效果
等等……要求dfs？但是前面说过dfs并不依赖于树，也就是说，我们可以不建树同时dfs，但是这要求我们掌握一个东西，即什么时候压栈，什么时候弹栈。再说的直白一点，我们需要欧拉序
欧拉序
什么是欧拉序，正常的dfs序仅在入栈的时候计算一次，而欧拉序，不仅在入栈的时候计算一次，还在出栈的时候计算一次，也就是说一个点有两次出现机会压栈为+，弹栈为-，欧拉序记录了dfs的全部信息，只要有了这个树的欧拉序，就算没有树，给我们一个栈，照样可以在树上跑dfs
本体题解
其实话已经说了一半了，我们发现，抽出来的那只树，它的欧拉序大小关系和原来的树的欧拉序是一样的，所以只需要把所有点的复制一个弹出点，然后把压栈点和弹栈点按原来树上的欧拉序排一波序，就是新树中的点按欧拉序排序的结果，然后欧拉序我们有了，直接不建树跑dfs即可，树形dp同暴力
注意这个算法复杂度不是Nlogsigma(K)因为我们是对一些小的数据排序，比合起来排一个大序的复杂度要小，另外你要真的觉得lca复杂度不行可以TARJAN，但是倍增常数真的小，可以过。
上代码~
#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;//开longlong
const int N=250010;
struct data{int v;int nxt;ll val;}edge[2*N];
int alist[N];int cnt;int n;
inline void add(int u,int v,ll val)
{edge[++cnt].v=v;edge[cnt].nxt=alist[u];alist[u]=cnt;edge[cnt].val=val;}
int dfu;int dfin[N];int dfou[N];int fa[22][N];ll mi[N];int dep[N];
inline void dfs(int x)//处理倍增和欧拉序
{
dfin[x]=++dfu;
for(int i=1;fa[i-1][x];i++){fa[i][x]=fa[i-1][fa[i-1][x]];}
int nxt=alist[x];
while(nxt)
{
int v=edge[nxt].v;ll val=edge[nxt].val;
if(dfin[v]==0)
{dep[v]=dep[x]+1;mi[v]=min(mi[x],val);fa[0][v]=x;dfs(v);}
nxt=edge[nxt].nxt;
}dfou[x]=++dfu;return;
}
inline int lca(int u,int v)//板子倍增，不会自行问度娘
{
if(dep[u]<dep[v])swap(u,v);int del=dep[u]-dep[v];
for(int i=0;del;del>>=1,i++){if(del&1){u=fa[i][u];}}if(u==v){return u;}
for(int i=20;i>=0;i--){if(fa[i][u]!=fa[i][v]){u=fa[i][u];v=fa[i][v];}}
return fa[0][v];
}int tr[4*N];stack <int> s;int m;bool book[N];ll sum[N];//用来还原dfs的栈
inline bool cmp(int x,int y)//按欧拉序排序
{int k1=(x>0)?dfin[x]:dfou[-x];int k2=(y>0)?dfin[y]:dfou[-y];return k1<k2;}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u;int v;int val;scanf("%d%d%d",&u,&v,&val);
add(u,v,val);add(v,u,val);
}mi[1]=0x7f7f7f7f;dfs(1);scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int cot;scanf("%d",&cot);
for(int j=1;j<=cot;j++)
{scanf("%d",&tr[j]);book[tr[j]]=true;sum[tr[j]]=mi[tr[j]];}//先处理关键点
sort(tr+1,tr+cot+1,cmp);//按dfs序排序
for(int j=1;j<cot;j++)//处理lca
{int lc=lca(tr[j],tr[j+1]);if(!book[lc]){tr[++cot]=lc;book[lc]=true;}}
int nc=cot;for(int j=1;j<=nc;j++){tr[++cot]=-tr[j];}//复制一个-的弹栈点
if(!book[1]){tr[++cot]=1;tr[++cot]=-1;}sort(tr+1,tr+cot+1,cmp);//强行加入1号
for(int j=1;j<=cot;j++)
{
if(tr[j]>0){s.push(tr[j]);}//模拟dfs
else
{
int now=s.top();s.pop();//pop掉之后剩下的栈顶就是父亲
if(now!=1){int fa=s.top();sum[fa]+=min(sum[now],mi[now]);}
else {printf("%lld\n",sum[1]);}//这里特判一下1
sum[now]=0;book[now]=false;//pop完之后记得清空
}
}
}return 0;//拜拜程序~
}