HDU 5566 Clarke and room (树链剖分,线段树,ac自动机)

给出一棵树,树上每个节点有一个名字字符串,有q个询问,计算树链u-v经过的点对应的字符串是si的子串的最大长度。

用树链剖分套一个线段树标记这些询问,线段树用vector存区间被那些编号的询问覆盖过。然后离线处理每棵线段树,每棵线段树套一个ac自动机,计算对应区间的所有字符串匹配对应询问的字符串的最大长度。

手搓将树链剖分的while(f1 != f2) 写成了if(f1 != f2) 然后检查了一个晚上。。。。。。。。

 

LEAVE A COMMENT