menu zcmimi's blog

arrow_back 基环树

```cpp

include

pragma GCC optimize(3)

define il inline attribute ((always_inline)

zc
2020-01-25 20:19

将一个骑士与他最痛恨的人连边

先考虑这个如果是树型dp:

f_x表示不取x,g_x表示取x

$$ fx=\sum \max(f{to},g_{to}) \ g_x=\sum

zc
2020-01-24 17:26

两次dp解决代替基环树dp

所有的A_i\rightarrow i构成了一棵基环树

我们先考虑如果基环树的子树怎么做

也就是树型dp

(f_x表示不放,g_x表示放)

若元素$i

zc
2020-01-24 16:39

求基环树直径

先找出环,把环当根节点,找出每棵子树的直径和最大深度d_x

接着就要在环上找到两点x,y使d_x+dis(x,y)+d_y最大

可以破环后用单调队列$\mathcal

zc
2020-01-24 00:21

```cpp

include<bits/stdc++.h>

namespace ZDY{

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