Open ManuShi98 opened 11 months ago
https://manushi98.github.io/2018/04/10/POJ%20-%202114%20Boatherds(%E7%82%B9%E5%88%86%E6%B2%BB)/
思路点分治裸题，但统计长度为k的路径时需要注意要使用O(n)的算法（我用了O(n^2)的居然没发现，TLE。。）具体思路就是先对depth排序，然后当depth[l]+depth[r]==k是，因为可能有与depth[l],depth[r]深度相同的，所以统计相同的个数直接numl*numr计算。若depth[l]+depth[r]<k那么l++，因为这时对当前的l能满足条件的r都已经计算过
https://manushi98.github.io/2018/04/10/POJ%20-%202114%20Boatherds(%E7%82%B9%E5%88%86%E6%B2%BB)/
思路点分治裸题，但统计长度为k的路径时需要注意要使用O(n)的算法（我用了O(n^2)的居然没发现，TLE。。）具体思路就是先对depth排序，然后当depth[l]+depth[r]==k是，因为可能有与depth[l],depth[r]深度相同的，所以统计相同的个数直接numl*numr计算。若depth[l]+depth[r]<k那么l++，因为这时对当前的l能满足条件的r都已经计算过