题解 P2495 【[SDOI2011]消耗战】

shadowice1984

2018-02-26 12:44:16

Solution

### 虚树 作为虚树的经典例题,拿这道题介绍一下虚树是什么好了~ #### 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号点除外) 那么我们可以把这种关系认为是父子关系,举个栗子 ![](https://cdn.luogu.com.cn/upload/pic/14884.png) 图中的红点是询问点,绿点是lca,蓝色的路径表示边,于是我们就从黑树中抽出了一只树同时保留了关于红点的全部信息 也就是说,对于这道题,我们可以建出这样的树,然后再这种树上跑dfs,就可以达到同样的树形dp效果 等等……要求dfs?但是前面说过dfs并不依赖于树,也就是说,我们可以不建树同时dfs,但是这要求我们掌握一个东西,即什么时候压栈,什么时候弹栈。再说的直白一点,我们需要欧拉序 ##### 欧拉序 什么是欧拉序,正常的dfs序仅在入栈的时候计算一次,而欧拉序,不仅在入栈的时候计算一次,还在出栈的时候计算一次,也就是说一个点有两次出现机会压栈为+,弹栈为-,欧拉序记录了dfs的**全部信息**,只要有了这个树的欧拉序,就算没有树,给我们一个栈,照样可以在树上跑dfs ### 本体题解 其实话已经说了一半了,我们发现,抽出来的那只树,它的欧拉序大小关系和原来的树的欧拉序是一样的,所以只需要把所有点的复制一个弹出点,然后把压栈点和弹栈点按原来树上的欧拉序排一波序,就是新树中的点按欧拉序排序的结果,然后欧拉序我们有了,直接不建树跑dfs即可,树形dp同暴力 注意这个算法复杂度不是Nlogsigma(K)因为我们是对一些小的数据排序,比合起来排一个大序的复杂度要小,另外你要真的觉得lca复杂度不行可以TARJAN,但是倍增常数真的小,可以过。 上代码~ ```C #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;//拜拜程序~ } ```