翻车笔记_ BZOJ1787 [Ahoi2008]Meet 紧急集合 [LCA, 结论]

有些结论看上去就是对的

懵逼的 题目

传送至 Bilibili

扯淡的 题解

闲的没事干(颓到自己想干正事了)的时候逛Menci的blog(Menci他老人家的blog上不去了_(:з」∠)_所以没有链接了_(:з」∠)_行吧又上去了)看到的…

结论:

  1. 三个点之间两两求LCA, 必定有至少两对LCA相等
  2. 那么离三个点最近的那个节点就是剩下的那一对的LCA
  1. 可以感性理解一下…如果”另一个”节点$Z$不在$LCA(X, Y)$的子树中, 那么$LCA(X, Z) == LCA(Y, Z)$这可以感性理解一下吧…而这个”另一个”节点我们是可以任意选择的…也就是说三个点之间的两两LCA至少两对相等
  2. Emmmmmmmm….如果把ans设为LCA, 那么如果ans向上移动一位, 就会使两个节点分别增加1距离, 而向下移动一位, 就一定要进入一棵子树, 同样会使总距离+1

看这张图可以更清晰一些

完了, 求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
/**************************************************************
Problem: 1787
User: Cansult
Language: C++
Result: Accepted
Time:3360 ms
Memory:65744 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (500000 + 5)
#define MAXL (20 + 5)
#define pii pair<int, int>
#define mkp(a, b) make_pair(a, b)
const int root = 1;
using namespace std;
struct edg
{
int from, to, next;
}b[MAXN << 1];
int g[MAXN], cntb, n, q, d[MAXN][MAXL], lgn, deep[MAXN];
void adn(int from, int to)
{
b[++cntb].next = g[from], b[cntb].from = from, b[cntb].to = to;
g[from] = cntb;
}
void dfs(int dq, int de)
{
deep[dq] = de;
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;
dfs(b[i].to, de + 1);
}
}
}
pii lca(int x, int y)
{
int re = 0;
if (deep[x] < deep[y])
swap(x, y);
for (int i = lgn; i >= 0; i--)
if (deep[d[x][i]] >= deep[y])
{
re += deep[x] - deep[d[x][i]];
x = d[x][i];
}
if (x == y)
return mkp(x, re);
for (int i = lgn; i >= 0; i--)
{
if (d[x][i] != d[y][i])
{
re += ((deep[x] - deep[d[x][i]]) << 1);
x = d[x][i], y = d[y][i];
}
}
return mkp(d[x][0], re + 2);
}
void solve()
{
for (int i = 1; i <= q; i++)
{
int x, xx, xxx;
scanf("%d%d%d", &x, &xx, &xxx);
pii lcaxy = lca(x, xx), llcaxy = lca(xx, xxx), lllcaxy = lca(xxx, x);
if (lcaxy.first == llcaxy.first) printf("%d %d\n", lllcaxy.first, lllcaxy.second + lca(lllcaxy.first, xx).second);
else if (llcaxy.first == lllcaxy.first) printf("%d %d\n", lcaxy.first, lcaxy.second + lca(lcaxy.first, xxx).second);
else if (lllcaxy.first == lcaxy.first) printf("%d %d\n", llcaxy.first, llcaxy.second + lca(llcaxy.first, x).second);
}
}
int lg(int x)
{
int re = 0;
for (; (1 << re) <= x; re++)
{}
return re;
}
int main()
{
scanf("%d%d", &n, &q);
lgn = lg(n);
for (int i = 1; i < n; i++)
{
int srx, sry;
scanf("%d%d", &srx, &sry);
adn(srx, sry);
adn(sry, srx);
}
d[root][0] = root;
dfs(root, 1);
solve();
return 0;
}

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

By Van了的 Cansult