[Luogu] p1395 meeting

Title address ：

https://www.luogu.com.cn/problem/P1395

Title Description ：
There is a village where $n$ A villager , Yes $n-1$ This path makes this $n$ It's a village home , The length of each path is $1$. Now the village head wants to hold a meeting in a villager's home , The village head hopes that the sum of the distance between all villagers and the meeting place will be the smallest , Then the village head should set the meeting place in which villager's home , And what is the minimum sum of this distance ？ If more than one node satisfies the condition , Then select the point with the smallest node number .

Input format ：
first line , a number $n$, Express $n$ A villager .
Next $n-1$ That's ok , Two Numbers per line $a$ and $b$, Represents the villagers $a$ Their homes and villagers $b$ There is a path between our homes .

Output format ：
Output two numbers on one line $x$ and $y$.
$x$ It means that the village head will hold a meeting in which villager's home .
$y$ Represents the minimum value of the sum of distances .

Data range ：
about $70\%$ data $n\le 10^3$.
about $100\%$ data $n\le 5\times 10^4$.

In fact, it is to find a point in the tree , Make the sum of the distance between the rest points to be minimum , If there are multiple and minimal points , Then take the one with the smallest number .

The answer is the center of gravity of the tree , Method reference https://blog.csdn.net/qq_46105170/article/details/113813152. Proof of nature reference https://blog.csdn.net/qq_46105170/article/details/125841504. Suppose we don't know the property , You can also solve .

You can do it twice DFS solve . set up $d[u]$ For all points and $u$ The sum of the distances . With $1$ Point number is the root of the tree , First pass DFS Find out each sub tree $v$ Number of nodes $s[v]$, Distance from all points $1$ The distance between the points $d[1]$. Second times DFS When , If $u\to v$, that $d[v]=d[u]+n-2s[u]$, thus $d[v]$ Can be $d[u]$ Push it out . Because it is known that $d[1]$, So that we can put $d$ The whole array is pushed out , to glance at $d$ Who is the smallest point . The code is as follows ：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 5e4 + 10, M = N << 1;
int n;
int h[N], e[M], ne[M], idx;
int sz[N], d[N];
int x, y;

void add(int a, int b) {
    
  e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs1(int u, int from, int dist) {
    
  sz[u] = 1;
  d[1] += dist;
  for (int i = h[u]; ~i; i = ne[i]) {
    
    int v = e[i];
    if (v != from) sz[u] += dfs1(v, u, dist + 1);
  }
  return sz[u];
}

void dfs2(int u, int from) {
    
  if (~from) {
    
    d[u] = d[from] + n - 2 * sz[u];
    if (d[u] < y) {
    
      y = d[u];
      x = u;
    } else if (d[u] == y) x = min(x, u);
  }

  for (int i = h[u]; ~i; i = ne[i]) {
    
    int v = e[i];
    if (v != from) dfs2(v, u);
  }
}

int main() {
    
  memset(h, -1, sizeof h);
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    
    int a, b;
    scanf("%d%d", &a, &b);
    add(a, b), add(b, a);
  }

  dfs1(1, -1, 0);
  //  Suppose the answer is 1 Number point 
  x = 1, y = d[1];
  dfs2(1, -1);
  printf("%d %d\n", x, y);
}

Complexity of time and space $O(n)$.