对于前50%50\%50%的数据,可以对每条边两边的点分别进行一次搜索来统计点数,时间复杂度为O(n2)O(n^2)O(n2)。
随意选一个点作为根,再以这个点出发构造有根树。在进行dfs时,每搜索完一条边,可以通过树的总节点数和子树的节点数快速计算出这条边两边节点个数的差异。时间复杂度为O(n)O(n)O(n)。
使用您的 Hydro 通用账户