牛客月赛112 d题

感觉d<c。
题意是：子节点数最多的节点的子节点数设为k，选择一个节点作为根节点，最小化k的值。
首先我们要清楚，一个节点成为根节点会改变什么。
我们假定一个节点和m个节点相邻。
如果这是一个非根节点，那么一定有1个节点是它的父节点，于是有m-1个节点是它的子节点。
而根节点是没有父节点的，也就是说，根节点的子节点个数会是m。
同时我们可以发现，不作为根的节点，无论其余节点谁做根节点，都不会影响它们的子节点个数。
也就是说，一定有一个节点（即根节点）的子节点数是m，其余节点的子节点数都是m-1，我们要让k最小，只要保证m最大的节点不做根节点就好。
这是一定能够保证的，因为一棵树一定会有m=1的叶子节点，不可能所有节点的m都是最大值。
除非m的最大值就是1，此时需要特判，想一下就知道是特判n=2的情况。

  1. 输入边，统计每个节点的相邻节点个数m。
  2. 特判n=2。
  3. 遍历所有节点，找到所有m的最大值。
  4. 题目要求根节点编号最小，所以从1号节点开始尝试，如果它的m是最大值就换下一个。
  5. 最小化后的k值即m的最大值-1，对应根节点编号即第四步找到的节点编号，输出即可。
#define ll long long
#include<bits/stdc++.h>
using namespace std;
int e[100005]={0};
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        e[u]++;
        e[v]++;
    }
    if(n==2){
        cout<<1<<" "<<1;
        return 0;
    }
    int mmax=0;
    for(int i=1;i<=n;i++){
        mmax=max(mmax,e[i]);
    }
    int r=1;
    while(e[r]==mmax) r++;
    cout<<mmax-1<<" "<<r;
    return 0;
}