前几天看到LCA，发现有种O(n)-O(1)的做法。本想找板子学习一下，苦寻无果。那就自己写写板子吧！因为实在才疏学浅，各位大佬要是遇到bug，或是wa的题。请告诉我！我去改！
//duobly On - O1 //顶点1-n #include
///*
int bin
[
23
]
;
int maxx
[
23
]
[maxn
]
;
int minx
[
23
]
[maxn
]
;
int lgg
[maxn
]
;
void
rangework
(
)
{
ST_buildmin
(n
)
;
ST_buildmax
(n
)
;
}
int
rangever
(
int x
,
int y
)
//区间lca查询
{
int L
=
ST_min
(x
, y
)
;
int R
=
ST_max
(x
, y
)
;
if
(L
> R
)
swap
(L
, R
)
;
return ver
[
querymin
(L
, R
)
]
;
}
void
ST_buildmin
(
int n
)
{
lgg
[
0
]
=
-
1
;
for
(
int i
=
1
; i
<= n
; i
++
) lgg
[i
]
= lgg
[i
/
2
]
+
1
; bin
[
0
]
=
1
;
for
(
int j
=
1
; j
<
23
; j
++
) bin
[j
]
= bin
[j
-
1
]
*
2
;
for
(
int i
=
1
; i
<= n
; i
++
)
{
minx
[
0
]
[i
]
= ind
[i
]
;
}
for
(
int i
=
1
; i
<= lgg
[n
]
; i
++
)
for
(
int j
=
1
; j
+ bin
[i
]
-
1
<= n
; j
++
) minx
[i
]
[j
]
=
min
(minx
[i
-
1
]
[j
]
, minx
[i
-
1
]
[j
+ bin
[i
-
1
]
]
)
;
}
void
ST_buildmax
(
int n
)
{
for
(
int i
=
1
; i
<= n
; i
++
)
{
maxx
[
0
]
[i
]
= ind
[i
]
;
}
for
(
int i
=
1
; i
<= lgg
[n
]
; i
++
)
for
(
int j
=
1
; j
+ bin
[i
]
-
1
<= n
; j
++
) maxx
[i
]
[j
]
=
max
(maxx
[i
-
1
]
[j
]
, maxx
[i
-
1
]
[j
+ bin
[i
-
1
]
]
)
;
}
int
ST_min
(
int x
,
int y
)
{
if
(x
> y
)
swap
(x
, y
)
;
int temp
= lgg
[y
- x
+
1
]
;
return
min
(minx
[temp
]
[x
]
, minx
[temp
]
[y
- bin
[temp
]
+
1
]
)
;
}
int
ST_max
(
int x
,
int y
)
{
if
(x
> y
)
swap
(x
, y
)
;
int temp
= lgg
[y
- x
+
1
]
;
return
max
(maxx
[temp
]
[x
]
, maxx
[temp
]
[y
- bin
[temp
]
+
1
]
)
;
}
//*/
}lca
;
int n
, m
;
int
main
(
)
{
lca
.
pre
(
)
;
//预处理
while
(
scanf
(
"%d"
,
&n
)
==
1
)
{
int u
, v
, d
; lca
.
init
(n
,
1
)
;
//重置
for
(
int i
=
0
; i
< n
-
1
; i
++
)
{
scanf
(
"%d%d"
,
&u
,
&v
)
; lca
.
addedge
(u
, v
,
0
)
;
//添加边
} lca
.
work
(
)
;
//lca处理 lca
.
rangework
(
)
;
//区域lca处理
//lca.lcadep(x, y); //祖先深度
//lca.lcaver(x, y); //祖先结点
scanf
(
"%d"
,
&m
)
;
int x
, y
;
for
(
int i
=
1
; i
<= m
; i
++
)
{
scanf
(
"%d%d"
,
&x
,
&y
)
;
printf
(
"%d\n"
, lca
.
rangever
(x
, y
)
)
;
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/204439.html原文链接：https://javaforall.net
