[某集训题]escape

这题还要再简单一点么?考场直接裸树剖秒了好么?

然后最后发现不会处理SCP-049-2的移动然后爆零0辣^_^

mdzz,出题人还问谁写了长链剖分啊,太工业了吧

……吓得我在角落瑟瑟发抖.

实际上两个dfs就可以解决的事情QAQ

对于SCP-049-2的移动就可以理解为找一个Mid,一旦超过这个Mid的距离然后就一定追不上的.

对于一个终点T,把所有符合条件的x标记出来,可以发现这些x正好是一颗子树x0的所有点

x与x0满足lca(x,x0)=x0且dep[x0]=dep[x]/2+1(令dep[1]=1)

然后dfs就好啦

[某集训题]escape》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注