[CTSC2018]暴力写挂

题目链接

两颗\(n\)个节点的树,求\(\max\limits_{1\le i\le n,1\le j\le n}\{depth(i)+depth(j)-depth(lca(i,j))-depth'(lca'(i,j))\}\)

\(depth(i)+depth(j)-depth(lca(i,j))\)其实可以看做\(dis(i,lca(i,j))+dis(i,lca(i,j))+dis(root,lca(i,j))\)。

考虑边分治。

对于分支中心\(z\)的子树维护\(f(x)=dis(x,root)\);
对于其他点维护\(g(y)\),表示从\(y\)到链\(root\rightarrow z\)的距离。

显然\(f(x)+g(y)=dis(x,lca)+dis(y,lca)+dis(root,lca)\)。

每一次分治对\(Tree2\)建虚树,在虚树上用儿子的\(f(x),g(x)\)更新父亲的,然后在每一个\(lca\)处更新答案,就相当于在\(lca’\)处讨论了所有最近公共祖先为\(lca’\)的点对,单次复杂度就降低到了\(O(n)\)。

时间复杂度\(O(nlogn)\)。


[CTSC2018]暴力写挂》有1条评论

  1. 请问博主能解释一下您这个虚树的写法吗?感觉好神奇啊,跑的好快。

Leave a reply