昔我往矣/树上乱搞/lca,树链剖分

题目链接:https://acm.ecnu.edu.cn/contest/354/problem/A/

 

原做法:树上倍增+lca,可能生成树的时候复杂度太高,用的是类似并查集的合并方式。

 

oj上的大佬:https://acm.ecnu.edu.cn/contest/354/submission/2247258/《树链剖分+lca》

先补一个变量vector https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html

跟着别人的程序修改,发现连续re那么多次,差别竟在 int dfs与void dfs。

!!!!!re可能是子程序用了函数。

 昔我往矣/树上乱搞/lca,树链剖分

 

按照别人的思路改完了。树链剖分。

树链剖分是用子树重量来求出重儿子son,再用son求出top,通过top进行快速跳转。

这里用到了一连串的函数。

vector(存边)-》dis,fa,deep,son,size,

dfs-》dfn-》pos

son-》top

lca《-dep,top,fa

以及路径长度式子:dis[a]+dis[b]-2*dis[lca]

 

经过模仿和思考,,,回到自己的解法。

树上倍增+lca。原来之前超时是因为预处理fa数组和di数组效率太低。当时采用并查集方法,要反复回溯,因此效率极低。

tip:建树建图多采用先存边后深搜构树。

昔我往矣/树上乱搞/lca,树链剖分

 

 树上倍增测试实例:耗时稍久。内存差异是因为之前抄了别人标称开5e5,实际上5e4足够。

 

上一篇:CF1447E Solution


下一篇:倍增求lCA