主题

主题

 
   

关于欧拉序表示路径的笔记

很早之前就听说过。今天好好学完了这一部分内容,参考的是jinlifu1999关于BZOJ4448的报告。

直接放结论好了。

如果用欧拉序(出栈入栈序),入栈用+x,出栈用-x来记录。在出栈入栈序中,一正一负会抵消。

那么一个点u到根root的路径Path(u,root)为Sum[u],Sum为欧拉序的前缀和。

由于一条路径是可以通过到根的路径来组合得到的,具体来说:

Path(u,v)=Path(u,root)+Path(v,root)-Path(lca,root)-Path(Fa[lca],root)

那么再欧拉序列上自然就可以表示为:

Path(u,v)=Sum[u]+Sum[v]-Sum[lca]-Sum[Fa[lca]]

注意在使用数据结构维护欧拉序列的时候,对Fa[lca]的调用要特判lca=root的情况。

不过这个玩意似乎用途不是那么地广泛。对于可加可减的运算,比方说“加”,“异或”这样的还是较好维护,也好写。但是一些奇奇怪怪的东西就比较难维护。可能需要参考《统计的力量》一文中一些奇奇怪怪的处理方法?

大概就是“加”和“异或”用比较方便。如果是其他的信息,强上数据结构也不见得不好。

 
 
评论