题目描述 Description

给出一棵树，求出树的中心。

为了定义树的中心，首先给每个结点进行标号。对于一个结点K，如果把K从树中删除（连同与它相连的边一起），剩下的被分成了很多块，每一块显然又是一棵树（即剩下的部分构成了一个森林）。则给结点K所标的号就是森林中结点个数最多的树所拥有的结点数。如果结点K的标号不大于其他任何一个结点的标号，则结点K被称为是树的中心。

输入描述 Input Description

输入：

输入的第一行包含一个整数N（1≤N≤16 000），表示树中的结点数。接下来N-1行，每个两个整数a,b，由一个空格分隔，表示a与b之间有一条边。

输出描述 Output Description

输出：

输出两行，第一行两个整数v,T，v表示树的中心结点的标号，T表示树有多少个中心。第二行包含T个数，为所有树的中心的编号，按升序排列。

样例输入 Sample Input

样例输入：

7

1 2

2 3

2 4

讯享网

1 5

5 6

6 7

样例输出 Sample Output

样例输出：

3 1

1

数据范围及提示 Data Size & Hint

数据范围: 20% N<=100 100% N<=16 000

分析

幸好之前在书上有看到过相关思路,so水过.(不要被事物的表面现象所迷惑),翻译一下题目,就是求一个点使以它为树根,满足最大子树的节点数最小.其实就是树的重心

思路:

1. 以1为根建树,在回溯时顺便求出子树的节点大小与子树孩子的最大值
2. 得出以上条件后可稍加分析,会发现一个特点:
   当以R为根节点的树转化为以R的孩子H为根节点时,只要令size[R]=n-size[H],size[H]=n即可维护子树的大小
3. So 题目要求的K即可表示为 K=max{ n-size[now],max( size[j] ) }
   其中,now为当前节点,j为now的children
4. 充分利用dfs的特性,在now节点处理完它的孩子后,直接用 3 的等式,更新ans

代码

#include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #define open(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout); #define close fclose(stdin); fclose(stdout);  using namespace std; struct node //树的节点 { 
     vector<int>ch; int d; // size int ma; //子树孩子的最大值 }; struct Edge //邻接表(链式向前星) { 
     int to; int next; }; int ank; // 找K值 vector<int>ans; //记录节点 int n; int cnt; int head[16005]; Edge edge[32005]; node tree[16005]; bool vis[16005]; inline int read() { 
     int k=1; int sum=0; char c=getchar(); for(;'0'>c || c>'9' ;c=getchar()) if(c=='-') k=-1; for(;'0'<=c && c<='9';c=getchar()) sum=sum*10+c-'0'; return sum*k; } inline void write(int x) { 
     if(x<0) { 
     putchar('-'); x*=-1; } if(x>9) write(x/10); putchar(x%10+'0'); } inline void add(int x,int y) { 
     ++cnt; edge[cnt].to=y; edge[cnt].next=head[x]; head[x]=cnt; } inline int max(int x,int y) { 
     return x>y?x:y; } inline void build(int p) { 
     for(int i=head[p];i;i=edge[i].next) // 建树 if(!vis[edge[i].to]) { 
     int y=edge[i].to; vis[y]=1; //初始化 tree[y].d=1; tree[p].ch.push_back(y); build(y); tree[p].d+=tree[y].d; //更新d/ma tree[p].ma=max(tree[p].ma,tree[y].d); } tree[p].ma=max(tree[p].ma,n-tree[p].d); // 更新答案 if(ank==-1 || tree[p].ma<ank) { 
     ank=tree[p].ma; ans.clear(); ans.push_back(p); }else if(tree[p].ma==ank) ans.push_back(p); } inline bool cmp(int x,int y) { 
     return x<y; } int main() { 
     open("tree"); n=read(); for(int i=1;i<n;++i) { 
     int x=read(),y=read(); add(x,y); add(y,x); } vis[1]=1; //初始化 tree[1].d=1; ank=-1; build(1); sort(ans.begin(),ans.end(),cmp); //答案要求 int s=ans.size(); write(ank);putchar(' ');write(s);putchar('\n'); for(int i=0;i<s;++i) { 
     write(ans[i]); putchar(' '); } close; return 0; } 

补充

树的重心相关知识点:

定义：使得最大子树的节点数最小的点
性质：
1.树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。
2.把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上
3.把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离
重要意义：
在对树进行分治的时候可以避免N^2的极端复杂度（从退化链的一端出发），保证NlogN的复杂度