menu zcmimi's blog

arrow_back LCA

树上差分,统计的时候每个节点都合并自身子节点的结果

每个点都维护一颗动态开点权值线段树

x\leftrightarrow y区间加可以看成x,yw位置+1,$lca(x,y),

zc
2020-03-01 14:52

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ 
zc
2019-12-21 19:47

思路很妙

注意m-n \le 20

也就是说最多只有21条非树边

我们可以先跑一遍kruskal,然后按套路建树,两点之间的距离就是d_x+d_y-2\times lca(x,y)

zc
2019-12-21 19:47

求出LCA

如果 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il
zc
2019-12-21 19:47
1 / 1
Search
search