给你一棵nn个节点的模板树,一棵大树初始等于模板树

给出mm次操作,每次把模板树中以xx为根的子树复制,并接到大树的yy号节点上

然后对新节点重标号,新节点的编号为大树在上一次操作结束时的节点数加上这个节点在模板树那棵子树里的排名

qq次询问,每次询问大树上两个节点的距离

n,m,q105n, m, q\le 10^5

LOJ 2050

Solution

一道大模拟题

对大树缩一下点,每次只保留复制过来子树的根结点,并处理出倍增数组。对于询问直接倍增求lca,一些细节地方暴力在模板树里求即可

对于求一个点在大树中具体的节点编号为多少,可以对模板树按dfs序建出主席树,直接查区间第

剩下的就全是特别屎的细节了

大概讲一些小地方吧:

注: 以下(包括代码中)的大点均表示大树在缩完点后剩下的点

  • 求lca的时候需要特殊处理一开始的两个端点到其对应的大点的距离;以及最后跳到大点lca的时候的细节问题

  • 要判断一下两个大点是否存在祖孙关系,画个图就会发现需要特判

  • 记得开long long

想了想还是扔张图上来吧

19-3-3-1

现在不是很想具体解释了,剩下的细节在代码注释里应该都有了,只是可能写的比较凌乱。。。

Code

把注释删掉之后还有6k,而且代码写得奇丑

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
238
239
240
241
242
243
244
245
246
247
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 2e5 + 100;

int N, M, Q;
int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1];
int fa[Maxn], dfn[Maxn], idfn[Maxn], dfs_clock, Root[Maxn];
int anc[22][Maxn], dep[Maxn], W[Maxn], size[Maxn];
vector <int> G[Maxn];

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls node[root].ch[0]
#define rs node[root].ch[1]
#define lson ls, l, mid
#define rson rs, mid + 1, r

struct info
{
int ch[2], cnt;
} node[Maxn * 60];
int node_cnt;

inline void build (int &root, int l, int r)
{
root = ++node_cnt;
if (l == r) return ;
build (lson), build (rson);
}

inline void insert (int pre, int &root, int l, int r, int x)
{
root = ++node_cnt;
node[root] = node[pre], ++node[root].cnt;

if (l == r) return ;
if (x <= mid) insert (node[pre].ch[0], lson, x);
else insert (node[pre].ch[1], rson, x);
}

inline int query (int pre, int root, int l, int r, int k)
{
if (l == r) return l;
int sum_left = node[ls].cnt - node[node[pre].ch[0]].cnt;
if (sum_left >= k) return query (node[pre].ch[0], lson, k);
return query (node[pre].ch[1], rson, k - sum_left);
}

#undef mid
#undef ls
#undef rs
#undef lson
#undef rson
}

map <int, int> S;
int Id[Maxn], fa_Id[Maxn], small_Id[Maxn];
// Id[i] 表示缩点之后的i号点在大树中的真实标号
// fa_Id[i] 表示缩点之后的i号点父亲在大树中的真实标号
// small_Id[i] 表示缩点之后的i号点在模板树中对应的标号

inline void dfs_pre (int x)
{
Id[x] = x, small_Id[x] = x;
idfn[dfn[x] = ++dfs_clock] = x;
dep[x] = dep[fa[x]] + 1, W[x] = W[fa[x]] + 1, size[x] = 1;
for (int i = 1; i <= 17; ++i) anc[i][x] = anc[i - 1][anc[i - 1][x]];

for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
if (y == fa[x]) continue;
fa[y] = fa_Id[y] = anc[0][y] = x;
dfs_pre (y);
size[x] += size[y];
}
}

inline void Init_Anc (int x, int f, int w)
{
fa[x] = anc[0][x] = f;
dep[x] = dep[f] + 1;
W[x] = W[f] + w;
for (int i = 1; i <= 17; ++i) anc[i][x] = anc[i - 1][anc[i - 1][x]];
}

inline int get_lca (int x, int y) // 计算模板树的lca
{
if (dep[x] < dep[y]) swap(x, y);
for (int i = 17; i >= 0; --i) if (dep[anc[i][x]] >= dep[y]) x = anc[i][x];
if (x == y) return x;
for (int i = 17; i >= 0; --i) if (anc[i][x] != anc[i][y]) x = anc[i][x], y = anc[i][y];
return anc[0][x];
}

inline int get_id (int x) // 获取一个大树中真实标号的点在模板树的对应标号
{
if (x <= N) return x;

int big_id = S.lower_bound (x) -> y;
int k = x - Id[big_id] + 1; //第k小
int small_id = small_Id[big_id];

int ans = SEG :: query (Root[dfn[small_id] - 1], Root[dfn[small_id] + size[small_id] - 1], 1, N, k);
return ans;
}

int is_anc, lca; // 记录LCA下面的那一个大点

inline int get_dis (int x, int y) // 计算两个大点的距离
{
int ans = W[x] + W[y];
if (dep[x] < dep[y]) swap(x, y);
is_anc = x;

for (int i = 17; i >= 0; --i) if (dep[anc[i][x]] > dep[y]) x = anc[i][x], is_anc = x;

if (dep[x] > dep[y]) x = anc[0][x];

if (x == y) { lca = x; return ans - 2 * W[x]; }
is_anc = 0;

for (int i = 17; i >= 0; --i) if (anc[i][x] != anc[i][y]) x = anc[i][x], y = anc[i][y];

int fa_x = get_id (fa_Id[x]), fa_y = get_id (fa_Id[y]);

int dis_small = W[get_lca (fa_x, fa_y)] - W[small_Id[anc[0][x]]]; // 两个小点的lca与上面那个大点的距离
ans -= 2 * W[anc[0][x]];
ans -= 2 * dis_small;

return ans;
}

inline int query (int x, int y) // 计算两个大树中真实标号点的距离
{
int id_x = S.lower_bound (x) -> y, id_y = S.lower_bound (y) -> y; // 所在大点的编号

int small_x = get_id (x), small_y = get_id (y); // 在模板树中对应编号

if (id_x == id_y) return W[small_x] + W[small_y] - 2 * W[get_lca(small_x, small_y)];

is_anc = 0;
int ans = get_dis (id_x, id_y);
int dis_x = W[small_x] - W[small_Id[id_x]]; // x与其大点的距离
int dis_y = W[small_y] - W[small_Id[id_y]];
if (!is_anc) return ans + dis_x + dis_y;

if (id_x != lca) swap (x, y), swap(small_x, small_y), swap(id_x, id_y), swap(dis_x, dis_y);
is_anc = get_id(fa_Id[is_anc]);
ans -= 2 * (W[get_lca (is_anc, small_x)] - W[small_Id[id_x]]);
ans += dis_x + dis_y;

return ans;
}

inline void Solve ()
{
dfs_pre (1);
SEG :: build (Root[0], 1, N);
for (int i = 1; i <= N; ++i)
{
S[i] = i;
SEG :: insert (Root[i - 1], Root[i], 1, N, idfn[i]);
}

int node_cnt = N;
for (int i = N + 1; i <= N + M; ++i)
{
int x = read<int>(), y = read<int>();
fa_Id[i] = y, small_Id[i] = x, Id[i] = node_cnt + 1;
S[node_cnt + size[x]] = i;
node_cnt += size[x];

if (y <= N) Init_Anc (i, y, 1);
else
{
int ff = S.lower_bound(y) -> y;
int small = get_id(y);
int dis = W[small] - W[small_Id[ff]] + 1;

Init_Anc (i, ff, dis);
}
}

while (Q--)
{
int x = read<int>(), y = read<int>();
printf("%lld\n", query(x, y));
}
}

inline void Input ()
{
N = read<int>(), M = read<int>(), Q = read<int>();
for (int i = 1; i < N; ++i)
{
int x = read<int>(), y = read<int>();
add_edge (x, y);
add_edge (y, x);
}
}

main()
{

#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}