树是一种很牛X的数据结构，性质有很多，比如（自行百度去）
今天主要讲一下如何求树的重心和直径（在某些算法中要用到）
1.树的重心
树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡（百度百科）
树的重心在点分治中可以保证递归的次数为log级别，保证代码不被卡。
求树的重心主要是利用了DP的思想，size[x]表示以i点为根节点的子树的节点数，f[x]表示以x为根节点时，节点最多的子树节点数是多少
注意最后f[x]要在f[x]与sum-size[x]中去max（sum是节点总数）
刚开始任选一个点，递归更新即可
·一道板子题 POJ 1655 CODE
#include<cstdio> #include<cstring> using namespace std; const int N=20005; struct edge { int to,next; }e[N*2]; int head[N],t,n,i,x,y,k,size[N],f[N],root,MIN; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline void write(int x) { if (x/10) write(x/10); putchar(x%10+'0'); } inline void add(int x,int y) { e[++k].to=y; e[k].next=head[x]; head[x]=k; } inline int max(int a,int b) { return a>b?a:b; } inline void getroot(int now,int fa) { size[now]=1; f[now]=0; for (int i=head[now];i!=-1;i=e[i].next) if (e[i].to!=fa) { getroot(e[i].to,now); size[now]+=size[e[i].to]; f[now]=max(f[now],size[e[i].to]); } f[now]=max(f[now],n-size[now]); if (f[now]<MIN) root=now,MIN=f[now]; if (f[now]==MIN&&now<root) root=now; } int main() { read(t); while (t--) { k=root=0; MIN=1e9; memset(e,-1,sizeof(e)); memset(head,-1,sizeof(head)); read(n); for (i=1;i<n;++i) { read(x); read(y); add(x,y); add(y,x); } getroot(1,-1); write(root); putchar(' '); write(MIN); putchar(' '); } return 0; }
2.树的直径，就是带权树上距离最远的两点
求法很简单，先任选一点做一次BFS，找出与它距离最远的点，那么该点就是树的直径的一个端点
再以此端点为起点再做一次BFS，找出与它距离最远的点，那么另一个点就是树的直径的另一个端点，它们之间的距离就是树的直径
1 设u为s-t路径上的一点，结论显然成立，否则设搜到的最远点为T则
dis(u,T) >dis(u,s) 且 dis(u,T)>dis(u,t) 则最长路不是s-t了，与假设矛盾
2 设u不为s-t路径上的点
首先明确，假如u走到了s-t路径上的一点，那么接下来的路径肯定都在s-t上了，而且终点为s或t，在1中已经证明过了
所以现在又有两种情况了：
1：u走到了s-t路径上的某点，假设为X，最后肯定走到某个端点，假设是t ，则路径总长度为dis(u,X)+dis(X,t)
2：u走到最远点的路径u-T与s-t无交点，则dis(u-T) >dis(u,X)+dis(X,t);显然，如果这个式子成立，
则dis(u,T)+dis(s,X)+dis(u,X)>dis(s,X)+dis(X,t)=dis(s,t)最长路不是s-t矛盾
(摘于CSDN dalao @大肥Fcx）
POJ 2631 树的直径裸题 CODE
#include<cstdio> #include<cstring> using namespace std; const int N=10005; struct egde { int to,next,v; }e[N]; int head[N],q[N],dis[N],x,y,z,k,ans; bool vis[N]; inline void add(int x,int y,int z) { e[++k].to=y; e[k].v=z; e[k].next=head[x]; head[x]=k; } inline int BFS(int now) { memset(vis,0,sizeof(vis)); int H=0,T=1,num; vis[now]=1; dis[now]=0; q[1]=now; ans=-1; while (H<T) { int x=q[++H]; if (dis[x]>ans) ans=dis[x],num=x; for (int i=head[x];i!=-1;i=e[i].next) if (!vis[e[i].to]) { vis[e[i].to]=1; dis[e[i].to]=dis[x]+e[i].v; q[++T]=e[i].to; } } return num; } int main() { //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout); memset(head,-1,sizeof(head)); memset(e,-1,sizeof(e)); while (scanf("%d%d%d",&x,&y,&z)!=EOF) add(x,y,z),add(y,x,z); BFS(BFS(1)); printf("%d",ans); return 0; }