倍增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
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
int f[N][30],d[N];
vector<int> G[N];
void dfs(int p,int fa)
{
d[p]=d[fa]+1;
f[p][0]=fa;
for(int i=1;(1<<i)<=d[p];i++)
f[p][i]=f[f[p][i-1]][i-1];
for(int i=0;i<G[p].size();i++)
if(G[p][i]!=fa)
dfs(G[p][i],p);
}
int LCA(int x,int y)
{
if(d[x]<d[y])
swap(x,y);
while(d[x]>d[y])
x=f[x][(int)log2(d[x]-d[y])];
if(x==y)
return x;
for(int i=log2(d[x]);i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
int main()
{
int n,m,s,l,r;
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++)
{
scanf("%d%d",&l,&r);
G[l].push_back(r);
G[r].push_back(l);
}
dfs(s,s);
while(m--)
{
scanf("%d%d",&l,&r);
printf("%d\n",LCA(l,r));
}
}
就算是一分钱,也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证
本文首发于baccano 博客( http://baccano.fun ),版权所有,侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆?---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%