Loj 2050 树

Posted on | Views:

主席树 + 倍增求 LCA.

显然不可能每次都老老实实栽一棵子树上去,我们每次只栽一个节点到大树中,代表这次栽的子树.

大树上每条边的边权就变成了儿子对应的根到父亲对应的根的距离,如图所示.

左边是大树的真实形态,红色的边是每次栽子树时加的边,黑色的边是模板树中原有的边.

右边是每次只栽一个节点上去得到的大树形态.

考虑如何在每次栽边后计算出右边新增加的边的权值.

记录下第 $i$ 次操作后,大树实际含有节点的总数 $s_i$ ,那么给出一个编号 $x$ 后,就可以二分出它是第几次被栽进来的.

若它是第 $i$ 次操作被栽进来的,那么 $k=x-s_{i-1}$ 就是它在第 $i$ 次被栽进来的所有点中,编号从小到大的位次.

即在模板树中,它是子树 $a_i$ 中所有节点编号的第 $k$ 小,用主席树可以查询出它在模板树中实际的编号.

对于每次操作,若栽在 $b$ 下面,就可以找出 $b$ 实际的编号,得到 $b$ 到那一次操作的 $a$ 的距离,再 $+1$ ,就是这次的边权.

询问 $(x,y)$ 时,尝试将它们跳到它们在大树上的 $lca$ ,跳的过程中累加跳过的距离.

先在右边的树上跳,若 $x,y$ 所属的代表节点没有祖先后代关系,当两者父亲相同时,说明已经被栽进了同一棵模板树.

此时将它们跳进模板树,再在模板树上询问两点的距离,加入答案.

若 $x,y$ 的代表节点有祖先后代关系,假定 $y$ 的代表是 $x$ 的代表的祖先,当 $x$ 跳到父亲是 $y$ 时,就可以跳进模板树了.

需要先预处理出父亲的倍增数组,加速跳的过程.

时间复杂度 $O(n\log n)$ .

其实这个结构与最后跳 $lca$ 的过程和圆方树有相似之处,对圆方树比较熟练的话应该不难写出.

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
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10,K=17;
int n,m,q;
namespace TempTree
{
	int ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1];
	void addedge(int u,int v)
	{
		++ecnt;
		to[ecnt]=v;
		nx[ecnt]=head[u];
		head[u]=ecnt;
	}
	int dep[MAXN],fa[MAXN][K],dfnidx=0,idx,dfn[MAXN],siz[MAXN];
	int rt[MAXN];
	struct node
	{
		int ls,rs,cnt;
	}Tree[MAXN*20];
#define root Tree[o]
	void upd(int &o,int lst,int l,int r,int pos)
	{
		o=++idx;
		root=Tree[lst];
		++root.cnt;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		if(pos<=mid)
			upd(root.ls,Tree[lst].ls,l,mid,pos);
		else
			upd(root.rs,Tree[lst].rs,mid+1,r,pos);
	}
	int query(int L,int R,int l,int r,int k)
	{
		if(l==r)
			return l;
		int mid=(l+r)>>1,tmp=Tree[Tree[R].ls].cnt-Tree[Tree[L].ls].cnt;
		if(tmp>=k)
			return query(Tree[L].ls,Tree[R].ls,l,mid,k);
		else
			return query(Tree[L].rs,Tree[R].rs,mid+1,r,k-tmp);
	}
	int FindNum(int x,int k)
	{
		return query(rt[dfn[x]-1],rt[dfn[x]+siz[x]-1],1,n,k);
	}
	int Dist(int x,int y)
	{
		int res=dep[x]+dep[y];
		if(dep[x]<dep[y])
			swap(x,y);
		for(int i=K-1;i>=0;--i)
			if((1<<i)<=dep[x]-dep[y])
				x=fa[x][i];
		if(x==y)
			return res-2*dep[x];
		for(int i=K-1;i>=0;--i)
			if((1<<i)<=dep[x] && fa[x][i]!=fa[y][i])
				x=fa[x][i],y=fa[y][i];
		return res-2*dep[fa[x][0]];
	}
	void dfs(int u,int F)
	{
		fa[u][0]=F;
		for(int i=1;(1<<i)<=dep[u];++i)
			fa[u][i]=fa[fa[u][i-1]][i-1];
		dfn[u]=++dfnidx,siz[u]=1;
		upd(rt[dfn[u]],rt[dfn[u]-1],1,n,u);
		for(int i=head[u];i;i=nx[i])
		{
			int v=to[i];
			if(v==F)
				continue;
			dep[v]=dep[u]+1;
			dfs(v,u);
			siz[u]+=siz[v];
		}
	}
	void init()
	{
		for(int i=1;i<n;++i)
		{
			int u=read(),v=read();
			addedge(u,v);
			addedge(v,u);
		}
		dfs(1,0);
	}
}
namespace BigTree
{
	ll s[MAXN],b[MAXN],dist[MAXN][K];
	int fa[MAXN][K],dep[MAXN],a[MAXN],c[MAXN];
	int FindTim(ll x,int cur)
	{
		int L=1,R=cur-1,tim;
		while(L<=R)
		{
			int mid=(L+R)>>1;
			if(s[mid]>=x)
				R=mid-1,tim=mid;
			else
				L=mid+1;
		}
		return tim;
	}
	int FindNum(ll x,int tim)
	{
		return TempTree::FindNum(a[tim],x-s[tim-1]);
	}
	void Link(ll B,int x)
	{
		int y=FindTim(B,x);
		fa[x][0]=y,dep[x]=dep[y]+1;
		int id=FindNum(B,y);
		c[x]=id;
		dist[x][0]=TempTree::Dist(id,a[y])+1;
	}
	int jump(int x,int d)
	{
		for(int i=K-1;i>=0;--i)
			if((1<<i)<=d)
				x=fa[x][i],d-=1<<i;
		return x;
	}
	ll query(ll A,ll B)
	{
		int x=FindTim(A,m+1),y=FindTim(B,m+1);
		int u=FindNum(A,x),v=FindNum(B,y);
		if(x==y)
			return TempTree::Dist(u,v);
		if(dep[x]<dep[y])
			swap(x,y),swap(A,B),swap(u,v);
		ll ans=0;
		if(jump(x,dep[x]-dep[y])==y)
		{
			ans+=TempTree::Dist(a[x],u);
			for(int i=K-1;i>=0;--i)
				if((1<<i)<=dep[x]-dep[y]-1)
					ans+=dist[x][i],x=fa[x][i];
			ans+=1;
			ans+=TempTree::Dist(c[x],v);
			return ans;	
		}
		ans+=TempTree::Dist(a[x],u)+TempTree::Dist(a[y],v);
		if(dep[x]<dep[y])
			swap(x,y);
		for(int i=K-1;i>=0;--i)
			if((1<<i)<=dep[x]-dep[y])
				ans+=dist[x][i],x=fa[x][i];
		for(int i=K-1;i>=0;--i)
			if((1<<i)<=dep[x] && fa[x][i]!=fa[y][i])
			{
				ans+=dist[x][i],ans+=dist[y][i];
				x=fa[x][i],y=fa[y][i];
			}
		ans+=2;
		ans+=TempTree::Dist(c[x],c[y]);
		return ans;
	}
	void solve()
	{
		++m,s[1]=n,a[1]=1;
		for(int i=2;i<=m;++i)
		{
			a[i]=read(),b[i]=read();
			s[i]=s[i-1]+TempTree::siz[a[i]];
			Link(b[i],i);
		}
		for(int i=1;i<=K-1;++i)
			for(int x=1;x<=m;++x)
				if((1<<i)<=dep[x])
				{
					fa[x][i]=fa[fa[x][i-1]][i-1];
					dist[x][i]=dist[x][i-1]+dist[fa[x][i-1]][i-1];
				}
		for(int i=1;i<=q;++i)
		{
			ll x=read(),y=read();
			printf("%lld\n",query(x,y));
		}
	}
}
int main()
{
	n=read(),m=read(),q=read();
	TempTree::init();
	BigTree::solve();
	return 0;
}