题目描述

如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：

深度：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 42 53 63 75 85 96 108 6

输出样例#1： 

448

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;int n,tot;struct edge{ int to; int next;}e[51];int head[101],deep[101],fa[101],size[101],son[101],top[101];int sum[101];inline void add(int x,int y){ e[++tot].to=y; e[tot].next=head[x]; head[x]=tot;}void dfs1(int now,int f,int deeep){//dfs1的目的是确定树的基础信息 deep[now]=deeep; fa[now]=f; size[now]=1; int maxson=-1; for(int i=head[now];i;i=e[i].next){ int y=e[i].to; if(y==f) continue; dfs1(y,now,deeep+1); size[now]+=size[y]; if(size[y]>maxson) maxson=size[y],son[now]=y;//记录重儿子 }}void dfs2(int x,int topf){//dfs2的目的是划分轻重链 top[x]=topf; if(!son[x]) return ; dfs2(son[x],topf); for(int i=head[x];i;i=e[i].next){ int y=e[i].to; if(y==fa[x]||y==son[x]) continue; dfs2(y,y); }} inline int lca(int x,int y){//树剖求LCA while(top[x]!=top[y]){//只要不在同一重链上 if(deep[top[x]]
             
              deep[y]) swap(x,y);//深度较小的就是LCA return x;}int main(){ scanf("%d",&n); for(int i=1;i