题目描述
如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：
深度：4 宽度：4（同一层最多结点个数）
结点间距离： ⑧→⑥为8 (3×2+2=8)
⑥→⑦为3 （1×2+1=3）
注：结点间距离的定义：由结点向根方向（上行方向）时的边数×2，
与由根向叶结点方向（下行方向）时的边数之和。
输入输出格式
输入格式：
输入文件第一行为一个整数n(1≤n≤100)，表示二叉树结点个数。接下来的n-1行，表示从结点x到结点y（约定根结点为1），最后一行两个整数u、v，表示求从结点u到结点v的距离。
输出格式：
三个数，每个数占一行，依次表示给定二叉树的深度、宽度及结点u到结点v间距离。
输入输出样例
输入样例#1：
10
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6
输出样例#1：
4
4
8
算法：
最近公共祖先（LCA）倍增
分析：
看题看了很久都没看懂，后来才发现这个是一个几乎lca的模板问题，只用把路径处理一下就好了，这里采用倍增的算法。
上代码：
#include<cstdio>
#define max(a,b) a>b?a:b
#define swap(a,b) a^=b^=a^=b
#define maxn 110
using namespace std; int n,m,s,tot,head[maxn],deep[maxn],p[maxn][],md,t[],ans;
struct node
{
int nxt,to;
}edge[maxn<<]; int read()
{
int x=,f=;
char c=getchar();
while (c<||c>)
f=c=='-'?-:,c=getchar();
while (c>=&&c<=)
x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
} void add(int a,int b)
{
edge[++tot]=(node){head[a],b};
head[a]=tot;
edge[++tot]=(node){head[b],a};
head[b]=tot;
} void init()
{
for (int j=;(<<j)<=n;j++)
for (int i=;i<=n;i++)
if (p[i][j-])
p[i][j]=p[p[i][j-]][j-];
} int dfs(int u)
{
for (int i=head[u];i;i=edge[i].nxt)
if (!deep[edge[i].to])
{
deep[edge[i].to]=deep[u]+;
p[edge[i].to][]=u;
dfs(edge[i].to);
}
} int LCA(int a,int b)
{
if (deep[a]<deep[b])
swap(a,b);
int i,j;
for (i=;(<<i)<=deep[a];i++);
i--;
for (j=i;j>=;j--)
if (deep[b]<=deep[a]-(<<j))
a=p[a][j];
if (a==b)
return a;
for (j=i;j>=;j--)
if (p[a][j]!=p[b][j]&&deep[p[a][j]]>=)
{
a=p[a][j];
b=p[b][j];
}
return p[a][];
} int main()
{
int i,j,k,u,v;
n=read();
for (i=;i<=n-;i++)
add(read(),read());
u=read(),v=read();
deep[]=;
dfs();
init();
for (i=;i<=n;i++)
md=max(md,deep[i]),t[deep[i]]++;
for (i=;i<=;i++)
t[]=max(t[],t[i]);
k=LCA(u,v);
ans=(deep[u]-deep[k])*+deep[v]-deep[k];
printf("%d\n%d\n%d",md,t[],ans);
return ;
}