本文参考自:https://oi-wiki.org/graph/tree-divide/#_2
https://www.cnblogs.com/Miracevin/p/10739810.html
边分治:顾名思义就是对边进行分治
具体过程类似点分:就是找一条边将这棵树尽可能均匀的分成两半,然后分别递归
但是遇到菊花图就完蛋了
所以我们可以像线段树那样,建立虚点,俗称三度化
见下图
然后再进行边分治,时间复杂度就对了
有朋友可能要问了:能点分为啥要边分?
这里就要发现边分治最重要的性质,如果你类似点分树那样,把边看成点,然后递归下去建树,你将得到一颗边分树,然后你会发现这是一棵二叉树!!!
二叉树能干吗,能干的事多了.
比如合并,还有只有两个儿子可以黑白染色,方便计算距离
看下面几 两道例题
原题给了你两棵树,要你求$max$ ($d1_x$ + $d1_y$ - $d1_{lca(x,y)}$ - $d2_{lca(x,y)}$)
d1,d2表示在两颗树中的深度.
考虑改写条件 ans = $max$ ($\frac{1}{2}$ ($dist1_{x,y}$ + $d1_x$ + $d1_y$ - 2 * $d2_{lca(x,y)}$))