20230512周五晚晚训cf_D题

(资料图)

总结

首先，递归一定要把返回值写全。有些编译器可能比较智能，比如vs，即使你的返回值没有写全，也会自动帮你补上。但是评测机上的编译器可能就没有这么智能，这时候，考验的就是你的代码规范性。

关于tree上子节点到根节点的距离，这个一定要熟练掌握。这个怎么算不容易出错一定要弄懂弄透。

出错原因：

返回值不全，导致判序函数可能无法正常运行。

算子节点到根节点距离的函数有些问题。导致程序出错。我出现的问题在哪里呢？就是我用了一个bool数组来存每一个节点是否被计算过。（假如没有这个数组的话，应该是会超时的）然而我的一个bug就是，dis数组（每个节点到根节点的总距离）不会再函数内部更新，只是在调用处才能更新一个值，也就是说，我好多结点已经被标记了，但是这些节点并没有dis值。

第三个问题，必须数值最小，否则一定超。也就是，不在同一枝的时候，一定要算出来最大值减去父节点的值。这样数值才不会爆。

题目链接：https://codeforces.com/gym/443080/problem/D

题解1:

我的这种思路时利用是否在同一枝上作为分类点，一种是不在同一枝时由到父节点的距离累加求和求根节点的距离反过来做差求新节点到父节点的距离，在同一枝的时候直接为1；

题解2：先把到根节点都定下来，再做差求子节点到父节点的距离。另外，是否符合顺序也可以通过父节点到根节点的距离是否更新过来进行判断。