yihouderen 2017-06-18 10:46 采纳率: 0%
浏览 1973
已结题

三星的上机题,请大神帮助解答。怎么打印出3到10000的数据。

You are to find the closest common ancestor of two vertices in a binary tree. For example, the common ancestors of vertices 8 and 13 in the figure below are vertices 3 and 1. Among them, vertex 3 is the closest to the vertex 8 and 13. And the size of sub-tree (the number of vertices in the sub-tree) rooted by vertex 3 is 8.图片说明
Given a binary tree and two vertices, write a program that finds the closest common ancestor and computes the size of the sub-tree rooted by the closest common ancestor. No input is given where one of the two given vertices is an ancestor of the other. For example, ‘11 and 3’ in the above tree is an invalid input. Therefore, your program does not have to consider this case.

[Constraints]
The number of vertices are from 3 to 10000

[Input]
You are given 10 test cases. Each test case has two lines, so the total number of lines is 20. In each test case, the first line consists of four integers, V (the number of vertices in the tree), E (the number of edges), and the indices of two vertices. E edges are listed in the next line. Each edge is represented by two vertices; the index of the parent vertex always precedes the index of the child. For example, the edge connecting vertices 5 and 8 is represented by “5 8”, not by “8 5.” There is no order in which the edges are given. Every consecutive integer in the input is separated by a space.

Given 10 test cases,
First 4 test cases contain small number of vertices(3, 5, 7, 10 each).
Next 6 test cases contain same or greater than 50 vertices.

The indices of vertices are integers from 1 to V, and root vertex always has the index 1.
It is guaranteed that the parent vertex has smaller index than the child vertex.
In this problem, it is not important whether the child is the left child of the parent or the right child; so you can decide this arbitrarily.

[Output]
Output 10 answers in 10 lines. Each line starts with ‘#x’ meaning the index of a test case, and writes the answer after a space. The answer has two integers: the index of the closest common ancestor and the size of the sub-tree rooted by the closest common ancestor. These two integers are separated by a space as well.

[I/O Example]
Input (20 lines in total)
13 12 8 13 ← Start of the first input
1 2 1 3 2 4 3 5 3 6 4 7 7 12 5 9 5 8 6 10 6 11 11 13
10 9 1 10 ← Start of the second input
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
...
Output (10 lines in total)
#1 3 8
#2 1 10
...

  • 写回答

2条回答 默认 最新

报告相同问题?

悬赏问题

  • ¥15 C#调用python代码(python带有库)
  • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B