关于虚树
瞎扯
某些树上问题，给了巨多节点，而实际上它们之中只有小部分能做出贡献，其余都是些水军，为杀尽 OIers的脑细胞 做出努力
考虑重新种一棵树，浓缩信息，简化节点个数，于是产生了 虚树。
大概是长这个样子：
红色结点是我们选择的关键点，即能够做出贡献的点。红色和黑色结点都是虚树中的点。黑色的边是虚树中的边。
因为任意两个关键点的 LCA 也是需要保存重要信息的，能够维持树的形态，所以我们需要保存它们的 LCA
显然，在保证爹不会变成儿子，儿子不会变成爹 爷爷也不行 的前提下，我们是可以随便把原有的点添到虚树中去的
你当然可以把原树所有的点都加到虚树中，只不过你这虚树建了跟建了一样
因此，为了方便，我们可以首先将 \(1\) 号节点加入虚树中，并且不会影响答案
构造
构造有两种方式，其中二次排序的方法常数较大，但是好记，也好理解。
另一种，则是借助单调栈实现的。
随个人喜好吧~
二次排序
很直观的思路。
首先将关键点按 \(DFS\) 序排序，枚举每个相邻的关键点，两两求得 \(LCA\) 并加入序列 \(\mathcal A\) 中。
此时序列 \(\mathcal A\) 中包含了虚树中的所有点，但是由于关键点的 \(LCA\) 可能相同，所以仍需去重。
因此我们把序列 \(\mathcal A\) 按照 \(DFS\) 序 从小到大排序并去重。
最后，在序列 \(\mathcal A\) 上，枚举相邻的两个点 \(x,y\)，求得它们的 \(LCA\) 并且连接 \(LCA(x,y),y\)，即可。
Code
int dfn[N];
int a[N],m,A[N],len;//m为关键点个数bool cmp(int x,int y){return dfn[x]<dfn[y];
} void build(){sort(a+1,a+1+m,cmp);for(int i=1;i<m;i++){A[++len]=a[i];A[++len]=lca(a[i],a[i+1]);}A[++len]=a[m];sort(A+1,A+1+len,cmp);len=unique(A+1,A+1+len)-A-1;for(int i=1;i<len;i++){addnew(lca(A[i],A[i+1]),a[i+1]);}
}
单调栈
直接枚举所有关键点对，暴力求解 LCA 的时间复杂度显然不可接受。
我们可以将所有关键点先按 DFS 序排序，按顺序一个一个加到树里。刚开始树上只有 \(1\) 号点。
接下来，我们用一个栈维护在树上一条链上的所有点。这个栈内的所有点满足其 DFS 序单调递增。
每次要将下一个关键点(设为 \(u\))入栈前，求一下当前栈顶元素和这个关键点 \(u\) 的LCA \(p\)，分讨：
-
如果栈顶是 \(p\)，则可以知道我们加入的关键点 \(u\) 和栈中的点在一条链上，直接将关键点加入栈中即可。如图
-
如果此时栈顶不是 \(p\)（显然这时候 \(p\) 的 DFS 序比栈顶大，且 栈顶所在位置的子树业已处理完毕），说明 \(p\) 不在链上，将栈顶弹出，直到栈顶为 \(p\)，此时插入关键点。
弹栈的时候记得把他和他父亲的边连一下。
左子树出栈
酱紫我们的虚树就种好了捏~
Code
bool cmp(int x,int y){return dfn[x]<dfn[y];
}int stk[N],top;
void build(){sort(a+1,a+1+k,cmp);stk[top=1]=1;for(int i=1;i<=k;i++){if(top==1){stk[++top]=a[i];}int lca=LCA(a[i],stk[top]);if(lca==stk[top]) continue;while(top>1 && dfn[stk[top-1]]>=dfs[lca]){addnew(stk[top-1],stk[top]);top--;}if(lca!=stk[top]){addnew(lca,stk[top]);stk[top]=lca;}stk[++top]=a[i];}while(top>0){//别忘了把栈里的连边addnew(stk[top-1],stk[top]);top--;}return;
}
例题
P2495 [SDOI2011] 消耗战
思路
把资源丰富的点看作关键点，建虚树。
对于阳历：
对于询问4 5 7 8 3构建出的虚树
考虑在虚树上DP。
令 \(f(u)\) 表示切断 \(u\) 的子树中的所有点的代价，\(mn(u)\) 表示从 \(u\) 到根节点的路径上最小的边权
分两种情况
如果 \(u\) 上边有资源，那么不管子树怎么样，\(u\)都要与根节点分离，即\(f(u)=mn(u)\)
否则就是 \(min(mn(u),\sum_{v=son[u]}f(v))\)
Code
这里是用单调栈实现的。
Elaina's Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rd read()
#define mkp make_pair
#define psb push_back
#define Elaina 0
#define random(a,b) (1ll*rand()*rand()*rand()%((b)-(a)+1)+(a))
inline int read(){int f=1,x=0;char ch=getchar();for(;!isdigit(ch);ch=getchar()) f=(ch=='-'?-1:1);for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';return f*x;
}
const int mod=998244353;
const int N=1e6+100;
const int inf=0x7fffffff7fffffff;int n,m,k,a[N];//原树
int h[N],idx;
struct EDGE{int to,nxt,w;
}e[N];void add(int x,int y,int z){e[++idx]=(EDGE){y,h[x],z};h[x]=idx;
}//虚树
int h1[N],idx1;
struct EDGE1{int to,nxt;
}e1[N];void addnew(int x,int y){e1[++idx1]=(EDGE1){y,h1[x]};h1[x]=idx1;
}int cnt,f[N],dfn[N],siz[N],son[N],topf[N],dep[N];
int mn[N];
void dfs1(int x,int fa){siz[x]=1;f[x]=fa;for(int i=h[x];i;i=e[i].nxt){int to=e[i].to;if(to==fa) continue;dep[to]=dep[x]+1;mn[to]=min(mn[x],e[i].w);dfs1(to,x);siz[x]+=siz[to];if(siz[to]>siz[son[x]]) son[x]=to;}
}void dfs2(int x,int topfa){topf[x]=topfa;dfn[x]=++cnt;if(!son[x]) return ;dfs2(son[x],topfa);for(int i=h[x];i;i=e[i].nxt){int to=e[i].to;if(!topf[to]){dfs2(to,to);}}
}int LCA(int x,int y){//树剖LCAwhile(topf[x]!=topf[y]){if(dep[topf[x]]<dep[topf[y]]) swap(x,y);x=f[topf[x]];}if(dep[x]<dep[y]) swap(x,y);return y;
}bool cmp(int x,int y){return dfn[x]<dfn[y];
}int stk[N],top;
void build(){//建虚树sort(a+1,a+1+k,cmp);stk[top=1]=1;for(int i=1;i<=k;i++){if(top==1){stk[++top]=a[i];}int lca=LCA(a[i],stk[top]);if(lca==stk[top]) continue;while(top>1 && dfn[stk[top-1]]>=dfn[lca]){addnew(stk[top-1],stk[top]);top--;}if(lca!=stk[top]){addnew(lca,stk[top]);stk[top]=lca;}stk[++top]=a[i];}while(top>0){addnew(stk[top-1],stk[top]);top--;}return;
}int dp[N];
int DP(int x){if(h1[x]==0) return mn[x];int ans=0;for(int i=h1[x];i;i=e1[i].nxt){int to=e1[i].to;ans+=DP(to);}h1[x]=0;return dp[x]=min(ans,1ll*mn[x]);
}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);mn[1]=1ll<<60;n=rd;for(int i=1;i<n;i++){int x=rd,y=rd,z=rd;add(x,y,z),add(y,x,z);}dep[1]=1;dfs1(1,0);dfs2(1,1);m=rd;while(m--){k=rd;for(int i=1;i<=k;i++) a[i]=rd;build();printf("%lld\n",DP(1));}return Elaina;
}
赏
就是说该吃饭了对吗？ 饿。
