1 //以一号节点为根节点，求出所有节点到根结点的距离，以及所有点的子节点的个数  2 //然后计算根据已知信息计算所有节点到当前结点的距离  3 //然后扫描n个点，O(n)求解  4 #include
     
       5 using namespace std; 6 const int maxn = 50086; 7 struct node { 8     int y, net; 9 }e[maxn << 1];10 int f[maxn], h[maxn];//h表示以当前节点的根结点的子节点的个数，f表示所有子节点到当前节点的距离和 11 int n;12 int lin[maxn], len = 0;13 int id;14 15 inline int read() {16     int x = 0, y = 1;17     char ch = getchar();18     while(!isdigit(ch)) {19         if(ch == '-') y = -1;20         ch = getchar();21     }22     while(isdigit(ch)) {23         x = (x << 1) + (x << 3) + ch - '0';24         ch = getchar();25     }26     return x * y;27 }28 29 inline void insert(int xx, int yy) {30     e[++len].y = yy;31     e[len].net = lin[xx];32     lin[xx] = len;33 }34 35 int son_num(int x, int fa) {36     for(int i = lin[x]; i; i = e[i].net) {37         int to = e[i].y;38         if(to != fa) h[x] += son_num(to, x) + 1;39     } 40     return h[x];41 }42 43 void everyson_to_one_dis(int x, int fa, int z) {44     f[1] += z;45     for(int i = lin[x]; i; i = e[i].net) {46         int to = e[i].y;47         if(to != fa) everyson_to_one_dis(to, x, z + 1);48     } 49 }50 51 void everyone_to_x_dis(int x, int fa) {52     f[x] = f[fa] - (h[x] + 1) + (n - h[x] - 1);53     for(int i = lin[x]; i; i = e[i].net) {54         int to = e[i].y;55         if(to != fa) everyone_to_x_dis(to, x);56     }57 }58 59 int main() {60     memset(lin, 0, sizeof(lin));61     n = read();62     for(int i = 1; i < n; ++i) {63         int x, y;64         x = read(), y = read();65         insert(x, y);66         insert(y, x);67     }68     son_num(1, 0);69     for(int i = lin[1]; i; i = e[i].net) 70         everyson_to_one_dis(e[i].y, 1, 1);71     for(int i = lin[1]; i; i = e[i].net)72         everyone_to_x_dis(e[i].y, 1);73     id = 1;74     for(int i = 2; i <= n; ++i)75         if(f[id] > f[i]) id = i;76     cout << id << ' ' << f[id] << '\n';77     return 0;78 }