作者:火影魂XJ_710 | 来源:互联网 | 2023-07-07 16:27
本博客主要是对前辈们的内容我认为好的部分摘取过来了《入门》LCA用轻重链剖分解决:好博客:https:www.cnblogs.comivanovcraftp9019090.html
本博客主要是对前辈们的内容我认为好的部分摘取过来了
《入门》
LCA用轻重链剖分解决:
好博客:https://www.cnblogs.com/ivanovcraft/p/9019090.html
https://www.luogu.com.cn/blog/by-random/solution-p3379








#include
#include
#include
#include
using namespace std;
const int N = 500010;
vector<int> tree[N];
int n, m, s;
//节点的父节点,重子儿子,深度,子树的大小
//规定:根节点dep=1,f=0; size包含自身;
int f[N], son[N], dep[N], size[N];
bool st[N];
//求出节点的f,son,dep,size
void dfs1(int s)
{
if (!st[s])
{
st[s] = true;
size[s] += 1;
int maxv = 0, v = s;
for (int i = 0; i )
{
int child = tree[s][i];
if (!st[child])
{
dep[child] = dep[s] + 1;
f[child] = s;
dfs1(child);
size[s] += size[child];
if (size[child] > maxv)
{
maxv = size[child];
v = child;
}
}
}
son[s] = v;
}
}
//规定:根节点top=自己,轻链top=自己
int top[N];
// dfs2将重链的链顶改变
void dfs2(int s)
{
if (!st[s])
{
st[s] = true;
for (int i = 0; i )
{
int child = tree[s][i];
if (!st[child] && son[s] == child)
top[child] = top[s];
dfs2(child);
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= n-1; i++)
{
int a, b;
scanf("%d%d", &a, &b);
tree[a].push_back(b), tree[b].push_back(a);
}
f[s] = 0, dep[s] = 1;
dfs1(s);
memset(st, false, sizeof(st));
for (int i = 1; i <= n; i++)
top[i] = i;
dfs2(s);
while (m--)
{
int a, b;
scanf("%d%d", &a, &b);
while (top[a] != top[b])
{
//将a与b跳到同一条链上
//指定a是dep[top[a]]更大的
if (dep[top[a]] < dep[top[b]])
swap(a, b);
a = f[top[a]];
}
int res = dep[a] a : b;
printf("%d\n", res);
}
return 0;
}