• 2024-08-0620240806:点分治,虚树选做
    POJ-1741Tree题意:给定一棵树,求多少无序对\((u,v)\)满足\(\text{dist}(u,v)\lek\)。对于树上的路径进行分类:经过根;不经过根。第二类路径点可以通过递归子树求出。对于经过根的路径,可以一遍dfs求出每个点到根的距离\(\text{dis}(u)\)。问题转化为求\(\text{dis}(u)