HNOI 2016 树（LCA+DFS序+主席树）

发表于 |
字数统计: 2,219字 | 阅读时长 ≈ 12min

[Hnoi2016 day1]树

问题描述

小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结点的编号为1,2,…,N，其中结点1为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下：（1）将模板树复制为初始的大树。（2）以下(2.1)(2.2)(2.3)步循环执行M次（2.1）选择两个数字a,b，其中1<=a<=N，1<=b<=当前大树的结点数。（2.2）将模板树中以结点a为根的子树复制一遍，挂到大树中结点b的下方(也就是说，模板树中的结点a为根的子树复制到大树中后，将成为大树中结点b的子树)。（2.3）将新加入大树的结点按照在模板树中编号的顺序重新编号。例如，假设在进行2.2步之前大树有L个结点，模板树中以a为根的子树共有C个结点，那么新加入模板树的C个结点在大树中的编号将是L+1,L+2,…,L+C；大树中这C个结点编号的大小顺序和模板树中对应的C个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图：

根据第(1)步，初始的大树与模板树是相同的。在(2.1)步，假设选择了a=4，b=3。运行(2.2)和(2.3)后，得到新的大树如下图所示

现在他想问你，树中一些结点对的距离是多少。

输入格式

第一行三个整数：N,M,Q，以空格隔开，N表示模板树结点数，M表示第(2)中的循环操作的次数，Q 表示询问数量。接下来N-1行，每行两个整数 fr,to，表示模板树中的一条树边。再接下来M行，每行两个整数x,to，表示将模板树中 x 为根的子树复制到大树中成为结点to的子树的一次操作。再接下来Q行，每行两个整数fr,to，表示询问大树中结点 fr和 to之间的距离是多少。N,M,Q<=100000

输出格式

输出Q行，每行一个整数，第 i行是第 i个询问的答案。

样例输入

5 2 3

1 4

1 3

4 2

4 5

4 3

3 2

6 9

1 8

5 3

样例输出

6

3

3

本题容易想到将每次选的树根连接成一颗树，每个点代表一块，然后先在这个树上倍增，走到同一块内后再到原树上倍增，想起来比较简单，但实现比较麻烦。

注意到需要通过新树中的编号查找在原树中的位置，由于知道当前块中树根的编号，等价于查询原树的一颗子树中的权值第$k$小，这个可以用DFS序转化成求序列上区间第$k$小，用主席树处理即可。

然后就是一堆细节，分块树上边的权值设成两个根之间的距离，倍增的时候要记下跳到了这一块中哪个节点上。

写起来非常的恶心!

代码：

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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 100005
#define int long long
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
int n,m,q;
namespace Seg
{
	int tot,ls[N<<7],rs[N<<7],v[N<<7];
	int CP(int p)
	{
		int o=++tot;
		ls[o]=ls[p];
		rs[o]=rs[p];
		v[o]=v[p];
		return o;
	}
	int ADD(int p,int l,int r,int k)
	{
		int o=CP(p);v[o]++;
		if(l==r)return o;
		int mid=l+r>>1;
		if(k<=mid)ls[o]=ADD(ls[o],l,mid,k);
		else rs[o]=ADD(rs[o],mid+1,r,k);
		return o;
	}
	int GA(int lp,int rp,int l,int r,int k)
	{
		if(l==r)return l;
		int mid=l+r>>1,tmp;
		tmp=v[ls[rp]]-v[ls[lp]];
		if(tmp>=k)return GA(ls[lp],ls[rp],l,mid,k);
		return GA(rs[lp],rs[rp],mid+1,r,k-tmp);
	}
}
namespace Ori
{
	int TOT,LA[N],NE[N<<1],EN[N<<1];
	int rt[N],fa[N][20],S=18,dep[N],In[N],Out[N],si[N],VT;
	void ADD(int x,int y)
	{
		TOT++;
		EN[TOT]=y;
		NE[TOT]=LA[x];
		LA[x]=TOT;
	}
	void DFS(int x,int f)
	{
		int i,y;
		if(f)dep[x]=dep[f]+1;
		In[x]=++VT;
		si[x]=1;
		fa[x][0]=f;
		rt[VT]=Seg::ADD(rt[VT-1],1,n,x);
		for(i=1;i<=S;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
		for(i=LA[x];i;i=NE[i])
		{
			y=EN[i];if(y==f)continue;
			DFS(y,x);si[x]+=si[y];
		}
		Out[x]=VT;
	}
	int LCA(int x,int y)
	{
		if(dep[x]<dep[y])swap(x,y);
		int i,t=dep[x]-dep[y];
		for(i=0;i<=S;i++)
		if(t>>i&1)x=fa[x][i];
		if(x==y)return x;
		for(i=S;i>=0;i--)
		if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
		return fa[x][0];
	}
	int DIS(int x,int y)
	{
		int lca=LCA(x,y);
		return dep[x]+dep[y]-(dep[lca]<<1);
	}
	int Getid(int x,int k)
	{return Seg::GA(rt[In[x]-1],rt[Out[x]],1,n,k);}
	int Getdep(int x,int k)
	{
		int p=Getid(x,k);
		return dep[p];
	}
}
namespace New
{
	int TOT,LA[N],NE[N],EN[N],LE[N];
	int rt[N],id[N],tot,All,fa[N];
	int dep[N],dis[N],F[N][20],S=18;
	void ADD(int x,int y,int z)
	{
		TOT++;
		EN[TOT]=y;
		LE[TOT]=z;
		NE[TOT]=LA[x];
		LA[x]=TOT;
	}
	void DFS(int x,int f)
	{
		int i,y;
		F[x][0]=f;
		dep[x]=dep[f]+1;
		for(i=1;i<=S;i++)F[x][i]=F[F[x][i-1]][i-1];
		for(i=LA[x];i;i=NE[i])
		{
			y=EN[i];if(y==f)continue;
			dis[y]=dis[x]+LE[i];DFS(y,x);
		}
	}
	int LCA(int x,int y)
	{
		if(dep[x]<dep[y])swap(x,y);
		int i,t=dep[x]-dep[y];
		for(i=0;i<=S;i++)
		if(t>>i&1)x=F[x][i];
		if(x==y)return x;
		for(i=S;i>=0;i--)
		if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
		return F[x][0];
	}
	int DIS(int x,int y)
	{
		int lca=LCA(x,y);
		return dis[x]+dis[y]-(dis[lca]<<1);
	}
	int Frt(int x)
	{
		int f=lower_bound(id+1,id+tot+1,x)-id;
		return id[f]==x?f:f-1;
	}
	void add(int x,int y)
	{
		id[++tot]=All+1;
		fa[tot]=y;
		rt[tot]=x;
		All+=Ori::si[x];
		int f=Frt(y);
		int k=Ori::Getdep(rt[f],y-id[f]+1)-Ori::dep[rt[f]];
		ADD(f,tot,k+1);
	}
	int GA1(int x,int y,int fx,int fy)
	{
		int i,j,k,sum=0,t=fx;
		int px=Ori::Getid(rt[fx],x-id[fx]+1);
		int py=Ori::Getid(rt[fy],y-id[fy]+1);
		sum+=Ori::dep[px]-Ori::dep[rt[fx]];
		k=dep[fx]-dep[fy]-1;
		for(i=0;i<=S;i++)
		if(k>>i&1)fx=F[fx][i];
		sum+=DIS(fx,t)+1;
		x=fa[fx];
		px=Ori::Getid(rt[fy],x-id[fy]+1);
		return sum+Ori::DIS(px,py);;
	}
	int GA2(int x,int y,int fx,int fy)
	{
		int lca=LCA(fx,fy),sum=0;
		sum+=Ori::Getdep(rt[fx],x-id[fx]+1)-Ori::dep[rt[fx]];
		sum+=Ori::Getdep(rt[fy],y-id[fy]+1)-Ori::dep[rt[fy]];
		int i,t=dep[fx]-dep[lca]-1;
		x=fx;y=fy;
		for(i=0;i<=S;i++)
		if(t>>i&1)fx=F[fx][i];
		sum+=DIS(x,fx);
		t=dep[fy]-dep[lca]-1;
		for(i=0;i<=S;i++)
		if(t>>i&1)fy=F[fy][i];
		sum+=DIS(y,fy);
		sum+=2;x=fa[fx];y=fa[fy];
		int px=Ori::Getid(rt[lca],x-id[lca]+1);
		int py=Ori::Getid(rt[lca],y-id[lca]+1);
		return sum+Ori::DIS(px,py);
	}
}
int main_main()
{
	int i,j,k,x,y,z,ans;
	_R(n);_R(m);_R(q);
	for(i=1;i<n;i++)
	{
		_R(x);_R(y);
		Ori::ADD(x,y);Ori::ADD(y,x);
	}
	Ori::DFS(1,0);
	New::id[New::tot=1]=1;
	New::All=n;New::rt[1]=1;
	for(i=1;i<=m;i++)
	{
		_R(x);_R(y);
		New::add(x,y);
	}
	New::DFS(1,0);
	for(i=1;i<=q;i++)
	{
		_R(x);_R(y);ans=0;
		int fx=New::Frt(x);
		int fy=New::Frt(y);
		if(fx==fy)
		{
			int px=Ori::Getid(New::rt[fx],x-New::id[fx]+1);
		    int py=Ori::Getid(New::rt[fy],y-New::id[fy]+1);
			ans=Ori::DIS(px,py);
		}
		else
		{
			int lca=New::LCA(fx,fy);
			if(lca==fx||lca==fy)
			{
				if(New::dep[fx]<New::dep[fy])swap(fx,fy),swap(x,y);
				ans=New::GA1(x,y,fx,fy);
			}
			else ans=New::GA2(x,y,fx,fy);
		}
		printf("%lld\n",ans);
	}
}
const int main_stack=16;    
char my_stack[128<<20];    
main() {    
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");    
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");    
  main_main();    
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");    
  return 0;    
}