虚树

发表于 | 分类于 | 阅读次数:
虚树，大概算是转载（见友链 ST）吧

概念

虚树可以用来解决在树上的多次询问，约束总询问点数的动态规划问题，相较直接BFS的高复杂度，虚树可以将开销降到与单次询问点数相关的时间复杂度之内。

常见的套路是有多次询问，每次询问的时间复杂度都可以接受，但乘上询问个数就十分恐怖，然而每次询问需要用到的点不多（一般每次询问的点数和有一个与点数同数量级的范围），这时候可以考虑每次建一棵虚树。

建树

考虑动态规划合并多个询问节点，只有在遍历到关键的 $lca$ 时才会计算贡献，且可以直接以 $lca$ 代替以下节点，所以可以设计出以下算法流程：

  1. 维护一个以 $\text{dfn}$ 序为关键字的单调栈，栈顶元素 $t_1$ 为所有已经处理过的节点中 $\text{dfn}$ 最大的节点，一般以根为初始节点，将所有询问节点按 $\text{dfn}$ 排序进行插入。
  2. 根据以上算法，一定有 $\text{dfn}[u]>\text{dfn}[t_1]​$ 。记栈顶第二个元素为 $t_2​$根据, $lca​$ 与 $t_2​$ 的关系进行分类讨论：
    • 当 $lca=t_2$ 时，将 $u$ 入栈。
    • 否则 $t_1$ 与 $t_2$ 分别在 lca 的两个子树中，则需要重复以下操作，直到 $p$ 到 $lca$ 中所有节点处理完毕，然后再将 $u$ 入栈。
      • 当 $\text{dfn}[t_2]>\text{dfn}[lca]$ 时，连边 $t_2\to t_1$, 弹出 $t_1$。
      • 当 $\text{dfn}[t_2]=\text{dfn}[lca]$ 时，连边 $lca\to t_1$. 此时 $t_1$ 到 $lca$ 已经处理完毕，即可跳出循环。
      • 当 $\text{dfn}[t_2]<\text{dfn}[lca]$ 时，此时 $lca$ 在 $t_2\to t_1$上，建边 $lca\to t_1$，以 $lca$ 代替pp在栈中的位置。此时 $t_1$ 到 $lca$ 已经处理完毕，即可跳出循环。

##模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int seq[MAXN],scnt;
int st[MAXN],tp;
void buildTree()
{
	int i;ecnt=0;
	std::sort(seq+1,seq+1+K,cmp);
	scnt=1;
	for(i=2;i<=K;i++) if(calLCA(seq[scnt],seq[i])!=seq[scnt])
		seq[++scnt]=seq[i];
	st[tp=1]=1;
	for(i=1;i<=scnt;i++)
	{
		int lca=calLCA(seq[i],st[tp]);
		while(dpt[st[tp-1]]>dpt[lca]) {addEdge(st[tp-1],st[tp]);tp--;}
		addEdge(lca,st[tp]);tp--;
		if(st[tp]!=lca) st[++tp]=lca;
		if(st[tp]!=seq[i]) st[++tp]=seq[i];
	}
	while(--tp) addEdge(st[tp],st[tp+1]);
}

注意每次建完虚树后都要清空，但不能用 memset 或 std::fill 之类无脑清导致复杂度爆炸，用多少清多少。

此写法为简化代码需要在 addEdge 函数中判 $u=v$ 的情况。

##[SDOI2011]消耗战

给定一棵 $n$ 个节点的树，每次

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
using std::swap;
typedef long long ll;
const int MAXN=25e4+5;const ll INF=1e18;

int N,M,K;

const int rt=1;
struct E{int next,to,val;} e[MAXN<<1];int ecnt,G[MAXN];
void addEdge(int u,int v,int w=0){if(u==v||!u||!v) return;e[++ecnt]=(E){G[u],v,w};G[u]=ecnt;}
void addEdge2(int u,int v,int w=0){addEdge(u,v,w);addEdge(v,u,w);}

ll mnv[MAXN],f[MAXN];
int dfn[MAXN],dcnt;int dpt[MAXN];
bool cmp(int a,int b){return dfn[a]<dfn[b];}

int anc[MAXN][20];
void dfs(int u)
{
	int i;dfn[u]=++dcnt;
	for(i=1;(1<<i)<=dpt[u];i++)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	for(i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==anc[u][0]) continue;
		mnv[v]=min(mnv[u],(ll)e[i].val);
		dpt[v]=dpt[u]+1;
		anc[v][0]=u;
		dfs(v);
	}
}

int calLCA(int x,int y)
{   
	int i;if(dpt[x]<dpt[y]) std::swap(x,y);
	for(i=19;i>=0;i--)
		if(dpt[x]-(1<<i)>=dpt[y])
			x=anc[x][i];
	if(x==y) return x;
	for(i=19;i>=0;i--)
		if(anc[x][i]!=anc[y][i])
			x=anc[x][i],y=anc[y][i];
	return anc[x][0];
}

int seq[MAXN],scnt;
int st[MAXN],tp;
void buildTree()
{
	int i;ecnt=0;
	std::sort(seq+1,seq+1+K,cmp);
	scnt=1;
	for(i=2;i<=K;i++) if(calLCA(seq[scnt],seq[i])!=seq[scnt])
		seq[++scnt]=seq[i];
	st[tp=1]=1;
	for(i=1;i<=scnt;i++)
	{
		int lca=calLCA(seq[i],st[tp]);
		while(dpt[st[tp-1]]>dpt[lca]) {addEdge(st[tp-1],st[tp]);tp--;}
		addEdge(lca,st[tp]);tp--;
		if(st[tp]!=lca) st[++tp]=lca;
		if(st[tp]!=seq[i]) st[++tp]=seq[i];
	}
	while(--tp) addEdge(st[tp],st[tp+1]);
}

void trDP(int u)
{
	f[u]=mnv[u];
	ll sum=0;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		trDP(v);
		sum+=f[v];
	}G[u]=0;
	if(sum==0)f[u]=mnv[u];
	else if(sum<=f[u])f[u]=sum;
}

int main()
{
	int i;
	scanf("%d",&N);
	for(i=1;i<N;i++)
	{
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		addEdge2(u,v,w);
	}
	mnv[rt]=INF;dfs(rt);
	memset(G,0,sizeof G);
	scanf("%d",&M);
	while(M--)
	{
		scanf("%d",&K);
        for(i=1;i<=K;i++) scanf("%d",seq+i);
        buildTree();
        trDP(rt);
        printf("%lld\n",f[rt]);
    }
    return 0;
}

##[Hnoi2014]世界树

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

const int MAXN=3e5+5;

int N,M,Q;

struct E{int next,to;} e[MAXN<<1];int ecnt,G[MAXN];
void addEdge(int u,int v){if(u==v) return;e[++ecnt]=(E){G[u],v};G[u]=ecnt;}
void addEdge2(int u,int v){addEdge(u,v);addEdge(v,u);}

int dfn[MAXN],dcnt;
bool cmp(int a,int b){return dfn[a]<dfn[b];}
int dpt[MAXN],sz[MAXN],anc[MAXN][20];
void dfs(int u)
{
	int i;dfn[u]=++dcnt,sz[u]=1;
	for(i=1;(1<<i)<=dpt[u];i++)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	for(i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==anc[u][0]) continue;
		dpt[v]=dpt[u]+1,anc[v][0]=u;
		dfs(v);
		sz[u]+=sz[v];
	}
}

int calLCA(int x,int y)
{
	int i;if(dpt[x]<dpt[y]) std::swap(x,y);
	for(i=19;i>=0;i--)
		if(dpt[x]-(1<<i)>=dpt[y])
			x=anc[x][i];
	if(x==y) return x;
	for(i=19;i>=0;i--)
		if(anc[x][i]!=anc[y][i])
			x=anc[x][i],y=anc[y][i];
	return anc[x][0];
}

int seq[MAXN],sseq[MAXN];
int st[MAXN],tp;
void buildTree()
{
	int i;ecnt=0;
	std::copy(seq+1,seq+1+M,sseq+1);
	std::sort(sseq+1,sseq+1+M,cmp);
	st[tp=1]=1;
	for(i=1;i<=M;i++)
	{
		int lca=calLCA(sseq[i],st[tp]);
		while(dpt[st[tp-1]]>dpt[lca]) {addEdge(st[tp-1],st[tp]);tp--;}
		addEdge(lca,st[tp]);tp--;
		if(st[tp]!=lca) st[++tp]=lca;
		if(st[tp]!=sseq[i]) st[++tp]=sseq[i];
	}
	while(--tp) addEdge(st[tp],st[tp+1]);
}

inline int calDis(int x,int y){return dpt[x]+dpt[y]-2*dpt[calLCA(x,y)];}

int blg[MAXN],lst[MAXN],lcnt,rst[MAXN];
void dfs1(int u)
{
	lst[++lcnt]=u;rst[u]=sz[u];
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		dfs1(v);if(!blg[v]) continue;
		if(!blg[u]){blg[u]=blg[v];continue;}
		int dv=calDis(u,blg[v]),du=calDis(u,blg[u]);
		if(dv<du||(dv==du&&blg[v]<blg[u])) blg[u]=blg[v];
	}
}

void dfs2(int u)
{
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!blg[v]) blg[v]=blg[u];
		else
		{
			int du=calDis(v,blg[u]),dv=calDis(v,blg[v]);
			if(du<dv||(du==dv&&blg[u]<blg[v])) blg[v]=blg[u];
		}
		dfs2(v);
	}
}

int ans[MAXN];
void dscs(int fa,int u)
{
	int i,son=u,mid=u;
	for(i=19;i>=0;i--)
		if(dpt[son]-(1<<i)>dpt[fa])
			son=anc[son][i];
	rst[fa]-=sz[son];
	if(blg[fa]==blg[u]) {ans[blg[fa]]+=sz[son]-sz[u];return;}
	for(i=19;i>=0;i--)
	{
		int nxt=anc[mid][i];if(dpt[nxt]<=dpt[fa]) continue;
		int df=calDis(nxt,blg[fa]),du=calDis(nxt,blg[u]);
		if(du<df||(du==df&&blg[u]<blg[fa])) mid=nxt;
	}
	ans[blg[fa]]+=sz[son]-sz[mid];
	ans[blg[u]]+=sz[mid]-sz[u];
}

const int rt=1;
int main()
{
	int i;
	scanf("%d",&N);
	for(i=1;i<N;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		addEdge2(u,v);
	}
	dfs(rt);
	memset(G,0,sizeof G);
	scanf("%d",&Q);
	while(Q--)
	{
		scanf("%d",&M);lcnt=0;
		for(i=1;i<=M;i++) scanf("%d",seq+i);
		buildTree();
		for(i=1;i<=M;i++) blg[seq[i]]=seq[i];
		dfs1(rt);
		dfs2(rt);
		for(int p=1;p<=lcnt;p++)
			for(i=G[lst[p]];i;i=e[i].next)
				dscs(lst[p],e[i].to);
		for(i=1;i<=lcnt;i++) ans[blg[lst[i]]]+=rst[lst[i]];
		for(i=1;i<=M;i++) printf("%d ",ans[seq[i]]);puts("");
		for(i=1;i<=lcnt;i++) ans[lst[i]]=rst[lst[i]]=G[lst[i]]=blg[lst[i]]=0;
	}
	return 0;
}