小型手机网站建设哪家好/小型培训机构管理系统

题意：求树的重心。树的重心为：去掉树上某节点形成的多棵树中节点的个数存在最大值，求这些最大值的最小值。如果这样的最小值有多个，那么输出序号最小的节点。直观理解，删除重心后，剩余的多棵树尽可能平衡。(3107:如果树有多个重心，求出所有的重心，并按照从小到大的顺序求出；2378：求把点删掉剩下的子树中最大的节点数不大于总点数一半的点)

思路：将树表示成有向树。设一共有n个节点，节点p引出t棵子树，每棵子树有节点son[1],son[2]...son[t]个。则此节点的值为max(son[1],son[2]...son[t],n-son[p]-1)。

用dfs来求son数组，dfs的过程中更新结果。

#include <stdio.h>
#include <string.h>
#define max(a,b) a>b?a:b
#define N 20005
struct node{int y,next;
}e[N*2];
int son[N],first[N],top,n,T,res1,res2;
void init(){memset(son,0,sizeof(son));memset(first,-1,sizeof(first));top =  0;res2 = 0x3fffffff;
}
void add(int x,int y){e[top].y = y;e[top].next  = first[x];first[x] = top++;
}
void dfs(int x,int father){int i,num=0;for(i = first[x];i!=-1;i=e[i].next)if(e[i].y != father){dfs(e[i].y,x);son[x] += son[e[i].y] + 1;num = max(num,son[e[i].y]+1);}num = max(num,n-son[x]-1);if(num < res2||(num<=res2&&x<res1)){res1 = x;res2 = num;}
}
int main(){freopen("a.txt","r",stdin);scanf("%d",&T);while(T--){int i,x,y;init();scanf("%d",&n);for(i = 1;i<n;i++){scanf("%d %d",&x,&y);add(x,y);add(y,x);}dfs(1,0);printf("%d %d\n",res1,res2);}return 0;
}

3107：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define N 50005
struct edge{int y,next;
}e[N<<1];
int n,top,m,len=0;
int first[N],son[N],res[N];
void add(int x,int y){e[top].y = y;e[top].next = first[x];first[x] = top++;
}
int cmp(const void* a,const void* b){return (*(int*)a)-(*(int*)b);
}
void dfs(int x,int fa){int i,y,num;son[x] = 1;num = 0;for(i = first[x];i!=-1;i=e[i].next){y = e[i].y;if(y!=fa && !son[y]){dfs(y, x);son[x] += son[y];num = max(num,son[y]);}}num = max(num, n-son[x]);if(num <= m){if(num < m){len = 0;m = num;}res[len++] = x;}
}
int main(){int i,a,b;memset(first, -1, sizeof(first));memset(son, 0, sizeof(son));top = 0;scanf("%d",&n);for(i = 1;i<n;i++){scanf("%d %d",&a,&b);add(a,b);add(b,a);}m = n;dfs(1,0);qsort(res,len,sizeof(int),cmp);for(i = 0;i<len-1;i++)printf("%d ",res[i]);printf("%d\n",res[len-1]);return 0;
}

2378：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define N 10005
struct edge{int y,next;
}e[N<<1];
int n,top,len=0;
int first[N],son[N],res[N];
void add(int x,int y){e[top].y = y;e[top].next = first[x];first[x] = top++;
}
int cmp(const void* a,const void* b){return (*(int*)a)-(*(int*)b);
}
void dfs(int x,int fa){int i,y,num;son[x] = 1;num = 0;for(i = first[x];i!=-1;i=e[i].next){y = e[i].y;if(y!=fa && !son[y]){dfs(y, x);son[x] += son[y];num = max(num,son[y]);}}num = max(num, n-son[x]);if(num <= n/2)res[len++] = x;
}
int main(){int i,a,b;top = 0;scanf("%d",&n);memset(first, -1, n*sizeof(int));memset(son, 0, n*sizeof(int));for(i = 1;i<n;i++){scanf("%d %d",&a,&b);add(a,b);add(b,a);}dfs(1,0);qsort(res, len, sizeof(int), cmp);for(i = 0;i<len;i++)printf("%d\n",res[i]);return 0;
}