【模板·树的重心】 codevs 3639 树的中心

题目：树的中心

树的重心

找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。

所以dfs下就好了。

代码：

#include<bits/stdc++.h>
using namespace std;#define maxn 16000
#define inf (1e9)
#define read(x) scanf("%d",&x)int n;
vector<int> tr[maxn+5];int d[maxn+5];
int minmaxd;
vector<int> ans;void readin() {
    read(n);for(int i=1;i<n;i++) {
    int x,y;read(x),read(y);tr[x].push_back(y);tr[y].push_back(x);}
}void dfs(int x,int fa) {
    d[x]=1;int maxd=0;for(int i=0;i<tr[x].size();i++) {
    if(tr[x][i]==fa) continue;dfs(tr[x][i],x);maxd=max(maxd,d[tr[x][i]]);d[x]+=d[tr[x][i]];}maxd=max(maxd,n-d[x]);if(maxd==minmaxd) ans.push_back(x);else if(maxd<minmaxd) {
    ans.clear();ans.push_back(x);minmaxd=maxd;}
}int main() {
    readin();minmaxd=inf;dfs(1,0);sort(ans.begin(),ans.end());printf("%d %d\n",minmaxd,ans.size());for(int i=0;i<ans.size();i++) printf("%d ",ans[i]);return 0;
}