题目描述
如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：
深度：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间距离。
无耻的借用洛谷的图片
这题就是个智障
首先dfs一下然后bfs一下然后lca一波就行了
一开始忘记讨论深度了然后使劲在那WA。。
//我知道不用写LCA和BFS但我就是想写你打我啊!!!!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<iterator> #include<queue> using namespace std; struct tr { int depth,father; }tree[110]={0}; struct ed { int pre,to; }edge[110]={0}; int nodenum,fx,tx,pointer[110]={0},at=0; int l[110][12]={0}; int answ=1,ansd=0; inline void Insert() { at++; edge[at].pre=pointer[fx]; edge[at].to=tx; pointer[fx]=at; } inline void bfs() { queue<int> que; int maxw=0,noww=0,cachen,prex; que.push(1); noww=1; while (!que.empty()) { cachen=que.front(); que.pop(); if (tree[cachen].depth==noww) maxw++; else { noww=tree[cachen].depth; answ=max(answ,maxw); maxw=1; } prex=pointer[cachen]; while (prex) { que.push(edge[prex].to); prex=edge[prex].pre; } } answ=max(answ,maxw); } void dfs(int nownode) { l[nownode][0]=tree[nownode].father; for (int i=1;i<=10;i++) l[nownode][i]=l[l[nownode][i-1]][i-1]; ansd=max(ansd,tree[nownode].depth); int prex=pointer[nownode]; while (prex) { dfs(edge[prex].to); prex=edge[prex].pre; } } inline int LCA(int u,int v) { for (int i=10;i>=0;i--) if (tree[l[u][i]].depth>=tree[v].depth) u=l[u][i]; if (u==v) return v; for (int i=10;i>=0;i--) if (l[u][i]!=l[v][i]) { u=l[u][i]; v=l[v][i]; } return tree[u].father; } int main() { scanf("%d",&nodenum); tree[1].father=-1; tree[1].depth=1; for (int i=1;i<nodenum;i++) { scanf("%d%d",&fx,&tx); tree[tx].father=fx; tree[tx].depth=tree[fx].depth+1; Insert(); } bfs(); dfs(1); printf("%d\n%d\n",ansd,answ); int un,vn,uvlca; bool flag=false; scanf("%d%d",&un,&vn); if (tree[un].depth<tree[vn].depth) { swap(vn,un); flag=true; } uvlca=LCA(un,vn); if (uvlca==un || uvlca==vn) { if (flag) printf("%d\n",tree[un].depth-tree[uvlca].depth); else printf("%d\n",2*(tree[un].depth-tree[uvlca].depth)); } else { if (!flag) printf("%d\n",2*(tree[un].depth-tree[uvlca].depth)+(tree[vn].depth-tree[uvlca].depth)); else printf("%d\n",2*(tree[vn].depth-tree[uvlca].depth)+(tree[un].depth-tree[uvlca].depth)); } return 0; } |