水题笔记_ [Hnoi2016]树 [LCA, 翻车, 主席树]

不动笔只是对着屏幕发呆是想不出解法的

不过…据说…晴天会让人心情好一些哦qwq

但是我为什么活的这么痛苦呢…

懵逼的 题目

qwq

扯淡的 题解

没什么用的思路

思路还是挺简单的…然而….

我们具体需要些啥呢…

  • 一个函数int qwq(LL x), 返回输入中的x所在的新节点的编号, 这个可以利用 前缀和×二分 搞一下
  • 一个函数int qwqwq(LL x), 返回输入的x在模板树中的编号, 这个可以…
    • 用一个数组rb[i]来记录第i个新节点包含的树(在模板树中)的树根
    • 建一棵主席树, int cx(int dq, int pre, int k)能够查询dfs序上一棵子树($[pre, dq]$)的第k大
    • 返回cx(root[ta[rb[qwq(x)]].end], root[ta[rb[qwq(x)]].begin - 1], x - fr_size[qwq(x)]);
  • 一个函数int lca(int x, int y), 返回在模板树中这两个点x, y的距离
  • 一个函数LL qwqlca(LL x, LL y), 返回在新树中这两个节点的距离
    • 一个数组cmt[x], 来记录x(新节点)通过(模板树中的)cmt[x]到达他的父亲, 也就是题目中的b1
    • 一个函数通过倍增求$LCA(x, y)$, 有三种情况
      1. $x, y$在一个新节点中: 直接找到他们在模板树中的编号, 然后返回其$LCA$即可
      2. $y$是$x$的祖先, 也就是没跳到深度相等, 就发现d[x][0] == y了: 返回cost + lca(cmt[x], qwqwq(y))(cost为已经跳过的距离)
      3. $x, y$在$LCA_{x, y}$不同的子树中: 返回cost + lca(cmt[x], cmt[y])

好像也就是这么点东西是不…

这里写图片描述

沙茶的 代码

好恶心…

  • 写主席树的时候…把左右边界写错了…居然还没看出来…

  • 不要忘记在加边权的时候, 新节点父亲的根不一定是模板树的根, 还要减一遍他真正根的深度

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
/**************************************************************
Problem: 4539
User: Cansult
Language: C++
Result: Accepted
Time:20968 ms
Memory:125292 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (100000 + 5)
#define MAXL (20 + 5)
#define pll pair<LL, LL>
#define LL long long
#define int LL
using namespace std;
struct edg
{
int from, to, next, cost;
};
struct hnode
{
int ls, rs, zh;
hnode(): ls(0), rs(0), zh(0) {}
};
struct tnode
{
int size, begin, end;
};
struct htree
{
hnode b[MAXN * 20];
int root[MAXN], cnt;
htree(): cnt(0) { memset(root, 0, sizeof(root)); }
void xg(int, int&, int, int, int);
int cx(int, int, int, int, int);
} hjt;
struct tree
{
edg b[MAXN << 1];
tnode ta[MAXN]; // 记录一个节点的子树
int n, lgn, d[MAXN][MAXL], deep[MAXN], g[MAXN], cntb, a[MAXN], cnta;
LL cost[MAXN];
tree(): cntb(-1), cnta(0) { memset(g, -1, sizeof(g)); }
int lg(int);
void dfs(int, int);
int lca(int, int); // 返回在模板树中这两个点x, y的距离
int tlca(int, int); // 返回两个点的lca
void adn(int, int, int);
} qwqo, qwqn; // 模板树, 新树
int n, m, cmt[MAXN], rb[MAXN]; // cmt[]: 来记录x(新节点)通过(模板树中的)cmt[x]到达他的父亲, 也就是题目中的b; rb[]: 来记录第i个新节点包含的树(在模板树中)的树根
LL fr_size[MAXN];
pll QAQsra[MAXN];
int qwq(LL); // 返回输入中的x所在的新节点的编号
int qwqwq(LL); // 返回输入的x在模板树中的编号
LL qwqlca(LL, LL); // 返回在新树中这两个节点的距离
main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("wa.out", "w", stdout);
#endif // ONLINE_JUDGE
int q;
scanf("%lld%lld%lld", &n, &m, &q);
qwqo.n = n, qwqn.n = ++m;
for (int i = 1, srx, sry; i < n; i++)
scanf("%lld%lld", &srx, &sry), qwqo.adn(srx, sry, 1), qwqo.adn(sry, srx, 1);
qwqo.d[1][0] = 1, qwqo.lgn = qwqo.lg(qwqo.n), qwqo.cost[1] = 0;
qwqo.dfs(1, 0);
for (int i = 1; i <= n; i++)
hjt.xg(hjt.root[i - 1], hjt.root[i], 1, n, qwqo.a[i]);
fr_size[1] = n, rb[1] = 1, cmt[1] = 1;
for (int i = 2; i <= m; i++)
scanf("%lld%lld", &QAQsra[i].first, &QAQsra[i].second),
fr_size[i] = fr_size[i - 1] + qwqo.ta[QAQsra[i].first].size;
for (int i = 2; i <= m; i++)
{
LL sra = QAQsra[i].first, srb = QAQsra[i].second;
int tb = qwqwq(srb), nb = qwq(srb), nc = qwqo.deep[tb] - qwqo.deep[rb[nb]] + 1; // 就是这个地方, 忘记减去qwqo.deep[rb[nb]]了
cmt[i] = tb, rb[i] = sra;
qwqn.adn(i, nb, nc); // 这里的cost其实是当前复制的根到他父亲的根的距离
qwqn.adn(nb, i, nc);
}
qwqn.d[1][0] = 1, qwqn.lgn = qwqn.lg(qwqn.n), qwqn.cost[1] = 0;
qwqn.dfs(1, 0);
for (int i = 1; i <= q; i++)
{
LL srx, sry;
scanf("%lld%lld", &srx, &sry);
printf("%lld\n", qwqlca(srx, sry));
}
return 0;
}
int qwq(LL x) // 返回输入中的x所在的新节点的编号
{
return lower_bound(fr_size + 1, fr_size + m + 1, x) - fr_size;
}
int qwqwq(LL x) // 返回输入的x在模板树中的编号
{
int bln = qwq(x), belong = rb[bln];
return hjt.cx(hjt.root[qwqo.ta[belong].begin - 1], hjt.root[qwqo.ta[belong].end], 1, qwqo.n, x - fr_size[bln - 1]);
}
int tree::lca(int x, int y) // 返回在模板树中这两个点x, y的距离
{
int re = cost[x] + cost[y];
return (re - (cost[tlca(x, y)] << 1));
}
LL qwqlca(LL bx, LL by) // 返回在新树中这两个节点的距离
{
int x = qwq(bx), y = qwq(by), lca = qwqn.tlca(x, y);
if (x == y)
return qwqo.lca(qwqwq(bx), qwqwq(by));
LL re = qwqn.cost[x] + qwqn.cost[y] - (qwqn.cost[lca] << 1);
re += qwqo.deep[qwqwq(by)] - qwqo.deep[rb[y]];
re += qwqo.deep[qwqwq(bx)] - qwqo.deep[rb[x]];
if (qwqn.deep[x] < qwqn.deep[y])
swap(x, y), swap(bx, by);
if (lca == y)
{
for (int i = qwqn.lgn; i >= 0; i--)
if (qwqn.deep[qwqn.d[x][i]] > qwqn.deep[y])
x = qwqn.d[x][i];
int olca = qwqo.tlca(cmt[x], qwqwq(by));
re -= (qwqo.deep[olca] - qwqo.deep[rb[lca]]) << 1;
return re;
}
else
{
for (int i = qwqn.lgn; i >= 0; i--)
if (qwqn.deep[qwqn.d[x][i]] >= qwqn.deep[y])
x = qwqn.d[x][i];
for (int i = qwqn.lgn; i >= 0; i--)
if (qwqn.d[x][i] != qwqn.d[y][i])
x = qwqn.d[x][i], y = qwqn.d[y][i];
int olca = qwqo.tlca(cmt[x], cmt[y]);
re -= (qwqo.deep[olca] - qwqo.deep[rb[lca]]) << 1;
return re;
}
}
void htree::xg(int pre, int& dq, int le, int ri, int zh)
{
dq = ++cnt;
if (le == ri)
{
b[dq].zh = b[pre].zh + 1;
return ;
}
int mi = (le + ri) >> 1;
if (zh > mi)
b[dq].ls = b[pre].ls, xg(b[pre].rs, b[dq].rs, mi + 1, ri, zh); // 这个地方...ri写成le了...
else
b[dq].rs = b[pre].rs, xg(b[pre].ls, b[dq].ls, le, mi, zh);
b[dq].zh = b[b[dq].ls].zh + b[b[dq].rs].zh;
}
int htree::cx(int pre, int dq, int le, int ri, int k)
{
if (le == ri)
return le;
int mi = (le + ri) >> 1, ka = b[b[dq].ls].zh - b[b[pre].ls].zh;
if (k <= ka)
return cx(b[pre].ls, b[dq].ls, le, mi, k);
else
return cx(b[pre].rs, b[dq].rs, mi + 1, ri, k - ka);
}
void tree::adn(int from, int to, int cost)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
b[cntb].cost = cost;
g[from] = cntb;
}
int tree::lg(int x)
{
int re = 0;
while ((1 << re) <= x)
++re;
return re + 1;
}
void tree::dfs(int dq, int de)
{
deep[dq] = de;
a[ta[dq].begin = ++cnta] = dq;
ta[dq].size = 1;
for (int i = 1; i <= lgn; i++)
d[dq][i] = d[d[dq][i - 1]][i - 1];
for (int i = g[dq]; ~i; i = b[i].next)
if (b[i].to != d[dq][0])
{
d[b[i].to][0] = dq, cost[b[i].to] = cost[dq] + b[i].cost;
dfs(b[i].to, de + 1);
ta[dq].size += ta[b[i].to].size;
}
ta[dq].end = cnta;
}
int tree::tlca(int x, int y)
{
if (deep[x] < deep[y])
swap(x, y);
for (int i = lgn; i >= 0; i--)
if (deep[d[x][i]] >= deep[y])
x = d[x][i];
if (x == y)
return x;
for (int i = lgn; i >= 0; i--)
if (d[x][i] != d[y][i])
x = d[x][i], y = d[y][i];
return d[x][0];
}

/*
10 2 6
1 2
1 3
2 10
3 4
3 5
4 6
4 7
7 8
7 9

4 10
2 5

15 12
15 11
15 5
16 5
15 17
11 17

5 2 3
1 4
1 3
4 2
4 5
4 3
3 2
6 9
1 8
5 3
*/

REfun妹子成群! REfun吊打学长!

By Cansult


  1. 1.(2.2)将模板树中以结点a为根的子树复制一遍,挂到大树中结点b的下方(也就是说,模板树中的结点a为根的子树复制到大树中后,将成为大树中结点b的子树