bzoj 2599 [IOI2011]Race

Posted by

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2599

题解

点分治:对于一个根节点,设\(t[i]\)表示之前遍历过的子树中深度为\(i\)的最小边数,\(d[u]\)表示\(u\)节点到根的边数,依次遍历每一个子树,用这两个数组更新\(ans\)即可,注意换根之前需要清空\(t[i]\)的值,不能用memset。

代码

Leave a Reply

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