Reincarnation

正因为梦易碎，才格外美好。

虚树

发表于 更新于 分类于 ，
本文字数： 14k 阅读时长 ≈ 12 分钟

恍若现实的倒影，唤醒未尽之篇章。

虚树

虚树，并不是用抽象的方式做树论的问题，而是通过重构一些关键结点来使本需要高复杂度解决的树论问题得到更好的解决。

思想

我们用一道题来引入：

题目简介

题目名称：消耗战
题目来源：山东省选 具体不详

评测链接：https://www.luogu.com.cn/problem/P2495

形式化题意：给定一棵有 个结点的树，边带权，一共 次询问，每次询问 个点，求断边的最小代价使得 号结点与这 个点都不连通。

数据范围：

首先我们考虑朴素的 ，设 表示以 为根的子树处理结束的最小代价，然后我们枚举 的儿子，可以得到以下转移：

  • 如果 不是关键点，；
  • 如果 是关键点，。

于是我们得到了一个 的做法。

然后你发现每次询问的关键点个数并不算多，大多数非关键点都是一个继承，转移基本无意义，而且很可能存在一棵很大的子树中一个关键点都没有，那这个时候 不纯属白给。所以我们希望有一个 的做法，每次询问的复杂度仅和关键点个数有关。

所以我们需要在这棵树上重构出一棵与关键点强相关的结点数尽量少的树，我们称之为虚树（）。

构建

我们考虑树上哪些结点会与关键点强相关，首先关键点肯定与自己强相关，然后目标点（在上题中为 号结点）也是，而根据转移，我们发现 也是必要的，否则我们不可能直接从根转移。

虚树的结点越多越稳，加入不必要的点不会影响正确性，只会影响常数与复杂度，而显然，原树就是自己最大的虚树。此时点数为 。

所以现在我们需要加入的三种点：关键点，目标点，关键点的 。

所以考虑怎么求 ，显然 枚举是报废的，所以我们先求出 序后将关键点按 排序求相邻的 后去重。

那么下一个问题是，在求得所有 后，我们怎么确定 之间的祖先关系呢？当然还是用 序。对于相邻的 ，我们连边 。

正确性证明？

摘自

如果 是 的祖先，那么 直接到 连边。因为 序保证了 和 的 序是相邻的，所以 到 的路径上面没有关键点。

如果 不是 的祖先，那么就把 当作 的祖先，根据上一种情况也可以证明 到 点的路径上不会有关键点。

所以连接 和 ，不会遗漏，也不会重复。

另外第一个点没有被一个节点连接会不会有影响呢？因为第一个点一定是这棵树的根，所以不会有影响，所以总边数就是 条。

找个什么方法求 ，构建过程就是 的，所以就得到了 的做法。

然后我们来做上面这道题，每次询问把虚树建出来后用朴素 即可，结点间的边权为原树上路径边权最小值，大家好我是暴力选手，所以我用线段树维护了最小边权。但是你倍增或者 表大概都是可以维护，只有我纯纯二货用树剖线段树。

时间复杂度 。记得不要在里面套 std::memset 之类的函数，否则会让复杂度假掉，尽量用哪些点改哪些点。

参考实现
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct Vtree
{
	struct Graph
	{ int next,to,val; }Edge[MAXN<<1];
	int Head[MAXN],Total;
	bool Pot[MAXN];
	inline void add(int u,int v,int w)
	{
		Edge[++Total]=(Graph){Head[u],v,w};Head[u]=Total;
		Edge[++Total]=(Graph){Head[v],u,w};Head[v]=Total;
	}
	ll Dp[MAXN];
	inline void build(std::vector<int>a)
	{
		std::sort(a.begin(),a.end(),cmp);
		std::vector<int>h;
		for(int i=1;i<(int)a.size();++i)
		{
			h.push_back(a[i-1]),
			h.push_back(getLca(a[i-1],a[i]));
		}
		h.push_back(a[(int)a.size()-1]),h.push_back(1);
		std::sort(h.begin(),h.end(),cmp);
		h.erase(std::unique(h.begin(),h.end()),h.end());
		for(int x:h) Head[x]=0,Dp[x]=0,Pot[x]=0;
		for(int x:a) Pot[x]=1;
		Total=0;
		for(int i=1;i<(int)h.size();++i)
		{
			int lc=getLca(h[i-1],h[i]);
			add(lc,h[i],getDist(lc,h[i]));
		}
	}
	void dpTree(int x,int last)
	{
		for(int e=Head[x],v;e;e=Edge[e].next)
		{
			if((v=Edge[e].to)==last) continue;
			dpTree(v,x);
			if(Pot[v]) Dp[x]+=Edge[e].val;
			else Dp[x]+=std::min(Dp[v],1ll*Edge[e].val);
		}
	}
	inline ll calc()
	{
		dpTree(1,0);
		return Dp[1];
	}
}Vt;

建树优化

后人发明了用单调栈维护建虚树的方法。根据 序的性质，如果相邻加入的结点在同一条链上，那么它们的 序也一定在一起。

所以考虑用单调栈维护虚树链。那么栈中相邻元素在虚树上同样是相邻的，且到栈顶的元素 序单调递增，而某个结点的父结点就是其之后下一个被弹出的元素。

然后考虑当前栈顶结点为 ，接下来加入结点 ，如果 的话，说明 是 的祖先结点，两个结点在同一条链上，直接入栈 。否则弹出栈顶元素 ，并与之后的栈顶元素连边，直到当前栈顶元素 有 。但如果有 ，此时要入栈 。

大概会比上一种方法跑的快些，但复杂度分析好像是一样的。

参考实现
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline bool cmp(int a,int b){ return dfn[a]<dfn[b]; }
inline void push(int x)
{ Stk[++Top]=x,Head[x]=0; }
inline void build(std::vector<int>a)
{
	std::sort(a.begin(),a.end(),cmp);
	push(1);
	for(int x:a)
		if(x!=1)
		{
			int lc=getLca(x,Stk[Top]);
			if(lc!=Stk[Top])
			{
				while(dfn[lc]<dfn[Stk[Top-1]]) add(Stk[Top-1],Stk[Top]),--Top;
				if(dfn[lc]>dfn[Stk[Top-1]]) push(lc);
				else add(lc,Stk[Top--]);
			}
			push(x);
		}
	for(int i=1;i<Top;++i) add(Stk[i],Stk[i+1]);
}

例题

虚树优化dp

题目简介

题目名称：大工程
题目来源：河北省选 第一天第三题（疑似）

评测链接：https://www.luogu.com.cn/problem/P4103

形式化题意：给定一个有 个结点的树，一共 次询问，每次询问 个结点，问这 个结点连成完全图，边权为原树距离的条件下：边权和，边权最大值，边权最小值。

数据范围：

还是先考虑朴素的 ，记录 表示以 为根的子树中有多少个关键点，那么对于边 就会贡献 。同理记录 表示子树边权最值。然后我们可以通过类似于维护树上直径的方式，维护子树距离最大值和次大值，因为显然边权最大值也肯定是树上的某一条直径，所以这样维护是正确的，那么用同样的方式也可以维护出最小值。

那么现在就有时间复杂度为 的做法，然后我们把这个方法搬到虚树上，就得到了 的 的做法。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
// ----- Eternally question-----
// Problem: P4103 [HEOI2014] 大工程
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4103
// Memory Limit: 500 MB
// Time Limit: 4000 ms
// Written by: Eternity
// Time: 2023-08-30 08:24:48
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1.5e6+10;
const int Inf=0x3f3f3f3f;
int N,Q;
struct G
{ int next,to; }Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Fa[MAXN],Siz[MAXN],Dep[MAXN],Son[MAXN],Dist[MAXN];
void dfsTree(int x,int last)
{
	Fa[x]=last,Dep[x]=Dep[last]+1,Siz[x]=1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		Dist[v]=Dist[x]+1;
		dfsTree(v,x);
		Siz[x]+=Siz[v];
		if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
	}
}
int Top[MAXN],Dfn[MAXN],Tot;
void dfsChain(int x,int topf)
{
	Top[x]=topf,Dfn[x]=++Tot;
	if(!Son[x]) return ;
	dfsChain(Son[x],topf);
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
		dfsChain(v,v);
	}
}
inline int getLca(int x,int y)
{
	while(Top[x]!=Top[y])
	{
		if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
		x=Fa[Top[x]];
	}
	return Dep[x]>Dep[y]?y:x;
}
inline bool cmp(int a,int b){ return Dfn[a]<Dfn[b]; }
std::vector<int>Ki;
bool Pot[MAXN];
int Cnt[MAXN],ansx,ansn,Fx[MAXN],Fn[MAXN];
ll anss;
void dpTree(int x,int last)
{
	if(Pot[x]) Cnt[x]=1,Fx[x]=Fn[x]=Dist[x];
	else Cnt[x]=0,Fx[x]=-Inf,Fn[x]=Inf;
	int px1=-Inf,px2=-Inf,pn1=Inf,pn2=Inf;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		dpTree(v,x);
		checkMax(Fx[x],Fx[v]),checkMin(Fn[x],Fn[v]);
		if(Fx[v]>=px1) px2=px1,px1=Fx[v];
		else checkMax(px2,Fx[v]);
		if(Fn[v]<=pn1) pn2=pn1,pn1=Fn[v];
		else checkMin(pn2,Fn[v]);
		anss+=1ll*Cnt[v]*((ll)Ki.size()-Cnt[v])*(Dist[v]-Dist[x]);
		Cnt[x]+=Cnt[v];
	}
	checkMin(ansn,pn1+pn2-2*Dist[x]);
	if(Pot[x]) checkMin(ansn,pn1-Dist[x]);
	checkMax(ansx,px1+px2-2*Dist[x]);
	if(Pot[x]) checkMax(ansx,px1-Dist[x]);
	Head[x]=0;
}
inline void build(std::vector<int>a)
{
	std::sort(a.begin(),a.end(),cmp);
	std::vector<int>h;
	for(int i=1;i<(int)a.size();++i)
	{
		h.push_back(a[i-1]);
		h.push_back(getLca(a[i-1],a[i]));
	}
	h.push_back(a[(int)a.size()-1]),h.push_back(1);
	std::sort(h.begin(),h.end(),cmp);
	h.erase(std::unique(h.begin(),h.end()),h.end());
	for(int x:a) Pot[x]=1;
	for(int i=1;i<(int)h.size();++i)
	{
		int lc=getLca(h[i-1],h[i]);
		addEdge(lc,h[i]);
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N),Dist[1]=1;
	for(int i=2,u,v;i<=N;++i) read(u,v),addEdge(u,v);
	dfsTree(1,0),dfsChain(1,1);
	std::memset(Head,0,sizeof(Head)),Total=0;
	read(Q);
	for(int ki;Q--;)
	{
		read(ki),Ki.clear();
		for(int i=1,x;i<=ki;++i) read(x),Ki.push_back(x);
		build(Ki);
		ansn=Inf,ansx=-Inf,anss=0;
		dpTree(1,0);
		write(anss,' ',ansn,' ',ansx,'\n');
		for(int x:Ki) Pot[x]=0;
	}
	return 0;
}
/*

*/

虚树优化dp II

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/contest/613/problem/D

形式化题意：给定一棵有 个结点的树，一共有 次询问，每次询问 个关键点，问至少需要删除多少个非关键结点才能使不存在两个关键结点连通。或报告无解。

数据范围：

首先考虑无解，那显然是存在两个关键点相连就无解。

然后考虑朴素 ，设 表示以 为根的子树中在处理结束后是否存在关键点与 相连，并用 表示以 为根的子树的最小代价。首先有 ，然后根据 判断：

  • 如果 是关键点，有 ，因为必须断掉，而 没法被删，就只能一个一个删 ；
  • 否则 不是关键点，而 ，所以直接删 即可，。
  • 然后就是 ，我们不知道删除 是否优，所以交给父结点判断。

时间复杂度 ，然后把这套做法搬到虚树上即可。时间复杂度 。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
// ----- Eternally question-----
// Problem: D. Kingdom and its Cities
// Contest: Codeforces - Codeforces Round 339 (Div. 1)
// URL: https://codeforces.com/contest/613/problem/D/
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-08-30 09:24:18
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int N,Q;
struct G
{ int next,to; }Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Fa[MAXN],Dep[MAXN],Siz[MAXN],Son[MAXN];
void dfsTree(int x,int last)
{
	Fa[x]=last,Dep[x]=Dep[last]+1,Siz[x]=1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		dfsTree(v,x);
		Siz[x]+=Siz[v];
		if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
	}
}
int Top[MAXN],Dfn[MAXN],Cnt;
void dfsChain(int x,int topf)
{
	Top[x]=topf,Dfn[x]=++Cnt;
	if(!Son[x]) return ;
	dfsChain(Son[x],topf);
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
		dfsChain(v,v);
	}
}
inline int getLca(int x,int y)
{
	while(Top[x]!=Top[y])
	{
		if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
		x=Fa[Top[x]];
	}
	return Dep[x]>Dep[y]?y:x;
}
inline bool cmp(int a,int b){ return Dfn[a]<Dfn[b]; }
std::vector<int>Ki;
bool Pot[MAXN],Con[MAXN];
int dpTree(int x,int last)
{
	int cnt=0,res=0;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		res+=dpTree(v,x);
		cnt+=Con[v];
	}
	if(Pot[x]) res+=cnt,Con[x]=1;
	else if(cnt>1) ++res,Con[x]=0;
	else Con[x]=cnt?1:0;
	Head[x]=Pot[x]=0;
	return res;
}
inline bool build(std::vector<int>a)
{
	std::sort(a.begin(),a.end(),cmp);
	std::vector<int>h;Total=0;
	for(int i=0;i<(int)a.size();++i) if(Pot[Fa[a[i]]]) return 0;
	for(int i=1;i<(int)a.size();++i)
	{
		h.push_back(a[i-1]);
		h.push_back(getLca(a[i-1],a[i]));
	}
	h.push_back(a[(int)a.size()-1]),h.push_back(1);
	std::sort(h.begin(),h.end(),cmp);
	h.erase(std::unique(h.begin(),h.end()),h.end());
	for(int i=1;i<(int)h.size();++i)
	{
		int lc=getLca(h[i-1],h[i]);
		addEdge(lc,h[i]);
	}
	return 1;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=2,u,v;i<=N;++i) read(u,v),addEdge(u,v);
	dfsTree(1,0),dfsChain(1,1);
	std::memset(Head,0,sizeof(Head)),Total=0;
	read(Q);
	for(int ki;Q--;)
	{
		read(ki),Ki.clear();
		for(int i=1,x;i<=ki;++i) read(x),Ki.push_back(x),Pot[x]=1;
		if(build(Ki)) write(dpTree(1,0),'\n');
		else
		{
			for(int x:Ki) Pot[x]=0;
			puts("-1");
		}
	}
	return 0;
}
/*

*/
相关文章