如何实现CF411D问题中的dfsdp离线二分算法？

本文共计2455个文字，预计阅读时间需要10分钟。

这个题目确实比较综合，也比较巧妙。首先，对于每个节点，需要计算以每个点为根的最大深度d。这样，在边界情况连续的时候，就可以直接更新直径。

这个方法可以通过两次DFS实现。首先进行一次DFS，计算所有节点的最大深度；然后进行第二次DFS，在更新直径的同时，也更新每个节点的最大深度。

主要维护前驱节点即可。

这个题确实比较综合，也非常巧妙。 。

首先对每棵树，需要算出以每个点为根的最大深度d，这样连边的时候就能直接更新直径。。这个可以用2遍dfs上搞搞下搞搞就行。。主要维护前2大深度。。

然后如果直接统计答案的话显然是不行的。。。但是如果和起来算有个问题是可能经过这条外加边形成的直径会比原直径小，那么先和起来算之后再关注比原直径小的情况。。很容易想到的一个做法是先对d排序，求前缀和，然后枚举其中一个子树的所有节点，然后在了另一个子树上进行二分找到比原直径小的部分，然后再进行计数。。这样复杂度是O(n^2logn)虽然实际复杂度没有这么大，不过还是比较危险。。

另一个优化角度就是枚举的时候枚举比较小的树，然而这样还是能被卡，卡的方式就是将点分配到2棵树上，重复询问，因此可先离线去重后再计数。这样一来只有子树是均摊才能使这个算法的复杂度最高，设n个点平均分配在了x个树上，那么复杂度为

实现巨麻烦。。还考验码力就很恶心了。。。怪不得没什么人过。。