http://blog.csdn.net/acdreamers/article/details/16905653
题意:给定一棵树,求树的重心的编号以及重心删除后得到的最大子树的节点个数size,如果size相同就选取编号最小的.
分析:首先要知道什么是树的重心,树的重心定义为:找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重
心后，生成的多棵树尽可能平衡. 实际上树的重心在树的点分治中有重要的作用, 可以避免N^2的极端复杂度（从退化链的一端出发），保证
NlogN的复杂度, 利用树型dp可以很好地求树的重心.
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 20000+5 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f #define ls (rt<<1) #define rs (rt<<1|1) int n,m; int ptr = 1,head[MAXN],vis[MAXN]; int res,ans,son[MAXN]; struct node { int y,val,next; }tree[MAXN<<1]; void add(int fa,int son) { tree[ptr].y = son; tree[ptr].next = head[fa]; head[fa] = ptr++; } void dfs(int root) { vis[root] = 1; son[root] = 0; int tmp = 0; for(int i=head[root];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y]) continue; dfs(y); son[root] += son[y]+1; tmp = max(son[y]+1,tmp); } tmp = max(tmp,n-son[root]-1); if(tmp<res || tmp == res && root < ans) { ans = root; res = tmp; } } int main() { int i,j,t,kase=1; sf("%d",&t); while(t--) { mem(tree,0); mem(head,-1); mem(vis,0); ans = INF,res=INF; ptr = 1; sf("%d",&n); int x,y; for(i=1;i<n;i++) { sf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1); pf("%d %d ",ans,res); } return 0; }
在这题里出现了这样一个情况，导致我第一次时TLE了
#define MAXN 20000+5 struct node { int y,val,next; }tree[MAXN*2];
因为是无向边，我习惯性地乘了2，导致结果错误。这里其实算出来的是20000+5*2 = 20010
改正有这样两种方法：
1.移位运算级低，可以直接用
#define MAXN 20000+5 struct node { int y,val,next; }tree[MAXN<<1];
2.define加括号
#define MAXN (20000+5) struct node { int y,val,next; }tree[MAXN*2];