关于虚树

\(\large 9.29\ upd:\)
更新了二次排序。

瞎扯

某些树上问题，给了巨多节点，而实际上它们之中只有小部分能做出贡献，其余都是些水军，~~为杀尽 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){//树剖LCA
	while(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;
}

赏

就是说该吃饭了对吗？饿。