zcmimi's blog

arrow_back基环树共7篇文章

avatar
zcmimi
2020-01-02

形态: 在一棵树上加多一条边

实现:

找出环后一次处理环上每个点的子树,然后再处理环

[IOI 2008]Island(求基环树直径)

IOI 2008 Island

先找出环,把环当根节点,找出每棵

avatar
zc
2020-06-14 13:07:00
查看原题

点击跳转

可以看出这是多颗基环树

分三种情况:

  1. x,y在不同的两颗树上

  2. x,y还没到达环就相遇了

  3. x,y的祖先在环上不同位置

avatar
zc
2020-01-25 20:19:00
查看原题

点击跳转

avatar
zc
2020-01-24 17:26:00
查看原题

点击跳转

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

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

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

f_x=\sum \max(f_{to},g_{to}) \\ g_x=\sum f_{to}

我们可以用两次树型dp代替基环树dp

第一次: 选择x,不选择x最痛恨的人

第一次: 选择x最痛恨的人,不选择x

avatar
zc
2020-01-24 16:39:00
查看原题

点击跳转

两次dp解决代替基环树dp

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

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

也就是树型dp

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

若元素i不投放,

f_x=\sum_{A_y=x}\max(f_y,g_y)

否则必须至少有一个元素限制i,不能投放

g_x=\max_{A_y=x}\{f_y+\sum_{A_z=x,z\not = y}\max(f_z,g_z)\}

找到环上的一个点,将它和它限制的那个点断开,先后进行两次树形dp,

第一次是假设环上的这个点对其限制的点不起限制作用

另外一次是强制环上那个点已经限制了其可以限制的点(也就是环上那个点不选)

avatar
zc
2020-01-24 00:21:00
查看原题

点击跳转

求基环树直径

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

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

可以破环后用单调队列\mathcal O(n)处理

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

1/1
Search
search