[LinttCode]The Barycentre Of The Trees

这道题和Fermat Point of Graphs是一样的，我们先选取任意节点当根节点，比如编号为0的节点，我们计算在这个情况下每个以i为根的subtree的size，记为size[i]。显而易见的是，size[i]  = sum(size[j]) + 1，j为i的子节点。我们用第一次DFS构建size数组。之后第二次我们同样从0号节点开始DFS，那么以r节点为根节点的情况下，r的所有子树中size最大的那一个res[r] = max(max(size[j]), N - size[i])，j是i的子节点，N为节点总数。我们取res中最大的那一个即可。
时间复杂度为建图和两次DFS，O(N)。空间复杂度同样，代码如下：