CF504E Misha and LCP on Tree
题：给出一棵
n
n
n结点的树，每个结点上有一个字符，
(
x
,
y
)
(x,y)
(x,y)表示从点
x
x
x到点
y
y
y路径上字符组成的字符串。有
q
q
q个查询，每个查询给出
a
,
b
,
c
,
d
a,b,c,d
a,b,c,d，求
(
a
,
b
)
(a,b)
(a,b)和
(
c
,
d
)
(c,d)
(c,d)的最长公共前缀。(
n
,
q
≤
300000
n,q\le300000
n,q≤300000)。
解：定义串
s
s
s的哈希函数为
h
s
(
s
)
=
∑
i
=
1
n
(
s
i
−
′
0
′
+
1
)
∗
b
a
s
e
i
hs(s)=\sum\limits_{i=1}^n(s_i-'0'+1)*base^i
hs(s)=i=1∑n(si−′0′+1)∗basei
定义
f
(
x
,
y
)
f(x,y)
f(x,y)为
(
x
,
y
)
(x,y)
(x,y)的哈希值。对于每一个结点
u
u
u，记录
f
(
1
,
u
)
f(1,u)
f(1,u)和
f
(
u
,
1
)
f(u,1)
f(u,1)。设点
s
s
s为
t
t
t的祖先，则
f
(
s
,
t
)
=
(
f
(
1
,
t
)
−
f
(
1
,
f
a
s
)
)
∗
i
n
v
(
b
a
s
e
d
e
p
s
−
1
)
f(s,t)=(f(1,t)-f(1,fa_s))*inv(base^{dep_s-1})
f(s,t)=(f(1,t)−f(1,fas))∗inv(basedeps−1)
f
(
t
,
s
)
=
f
(
t
,
1
)
−
b
a
s
e
d
e
p
t
−
d
e
p
s
∗
f
(
s
,
1
)
f(t,s)=f(t,1)-base^{dep_t-dep_s}*f(s,1)
f(t,s)=f(t,1)−basedept−deps∗f(s,1)同时，若
s
s
s和
t
t
t互不为祖先，求出其
l
c
a
lca
lca拆分出两条路径并采用，仍然可用上述方法
O
(
1
)
O(1)
O(1)求出哈希值。
从而，对于每个查询，求出
l
c
a
(
a
,
b
)
lca(a,b)
lca(a,b)和
l
c
a
(
c
,
d
)
lca(c,d)
lca(c,d)，二分
(
a
,
b
)
(a,b)
(a,b)和
(
c
,
d
)
(c,d)
(c,d)最长公共前缀的长度，长链剖分求
b
b
b和
d
d
d的
k
k
k级祖先，判断哈希值是否相等即可，时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。