x*8
2 楼
我家女儿7个多月了，由于最近冬天，天冷，有时候把尿她不尿，不把的时候马上把裤
子尿湿了。那天妈妈跟我说起这事，说妞妞这几天总是把裤子尿湿，怎么怎么的，结果
她就把头歪到我妈的胳膊上一趴，哭起来了。然后我妈就赶紧说，好了好了，不说你了
，然后人家就自己用袖子抹了一下眼睛，就不哭了。7个多月，懂什么啊，呵呵。
子尿湿了。那天妈妈跟我说起这事，说妞妞这几天总是把裤子尿湿，怎么怎么的，结果
她就把头歪到我妈的胳膊上一趴，哭起来了。然后我妈就赶紧说，好了好了，不说你了
，然后人家就自己用袖子抹了一下眼睛，就不哭了。7个多月，懂什么啊，呵呵。
i*r
3 楼
看不到题目，谁贴个题目来看看吧
b*8
4 楼
真是 太可爱了！
B*5
5 楼
这么快。。。
我一个好友进前100了。。。
我一个好友进前100了。。。
X*r
6 楼
呵呵，她未必真的理解话里的意思，但是有些小孩对语气很敏感。我家娃也是，很小就
知道说他的是好话还是坏话。
【在 x***8 的大作中提到】
: 我家女儿7个多月了，由于最近冬天，天冷，有时候把尿她不尿，不把的时候马上把裤
: 子尿湿了。那天妈妈跟我说起这事，说妞妞这几天总是把裤子尿湿，怎么怎么的，结果
: 她就把头歪到我妈的胳膊上一趴，哭起来了。然后我妈就赶紧说，好了好了，不说你了
: ，然后人家就自己用袖子抹了一下眼睛，就不哭了。7个多月，懂什么啊，呵呵。
知道说他的是好话还是坏话。
【在 x***8 的大作中提到】
: 我家女儿7个多月了，由于最近冬天，天冷，有时候把尿她不尿，不把的时候马上把裤
: 子尿湿了。那天妈妈跟我说起这事，说妞妞这几天总是把裤子尿湿，怎么怎么的，结果
: 她就把头歪到我妈的胳膊上一趴，哭起来了。然后我妈就赶紧说，好了好了，不说你了
: ，然后人家就自己用袖子抹了一下眼睛，就不哭了。7个多月，懂什么啊，呵呵。
p*2
7 楼
牛呀。
【在 B******5 的大作中提到】
: 这么快。。。
: 我一个好友进前100了。。。
h*u
8 楼
懂的比你想像的多，不过不会表达就是了
y*u
9 楼
我全挂。。。
【在 p*****2 的大作中提到】
:
: 牛呀。
【在 p*****2 的大作中提到】
:
: 牛呀。
x*8
10 楼
恩，是的，现在的娃娃就是很敏感啊。
【在 X****r 的大作中提到】
: 呵呵，她未必真的理解话里的意思，但是有些小孩对语气很敏感。我家娃也是，很小就
: 知道说他的是好话还是坏话。
【在 X****r 的大作中提到】
: 呵呵，她未必真的理解话里的意思，但是有些小孩对语气很敏感。我家娃也是，很小就
: 知道说他的是好话还是坏话。
l*a
11 楼
看来大牛又晋级了
admire
【在 p*****2 的大作中提到】
: 大家查查吧。谁进了下一轮吱一声呀。
admire
【在 p*****2 的大作中提到】
: 大家查查吧。谁进了下一轮吱一声呀。
x*8
12 楼
的确是啊，总感觉她小着呢，应该不懂，结果她有时候似乎懂了一样。呵呵
【在 h********u 的大作中提到】
: 懂的比你想像的多，不过不会表达就是了
【在 h********u 的大作中提到】
: 懂的比你想像的多，不过不会表达就是了
p*2
13 楼
我全挂了too。成都如果全挂我更没戏了。
【在 l*****a 的大作中提到】
: 看来大牛又晋级了
: admire
w*t
14 楼
很正常，我儿子小时候只要我和他爹说他什么，或者学他的声音，他立刻就哭
l*a
15 楼
share 一下题目，大家讨论一下吧
【在 p*****2 的大作中提到】
:
: 我全挂了too。成都如果全挂我更没戏了。
【在 p*****2 的大作中提到】
:
: 我全挂了too。成都如果全挂我更没戏了。
p*2
16 楼
In a certain business sector there are currently N small companies, each
having just a single employee. These employees are numbered 1 through N.
The business sector is about to be transformed into a monopoly. This will
happen through a series of mergers, until there is only one company. A
single merger involves two companies. In a merger, the president of one
company becomes the direct report of the president of the other company,
preserving the rest of the hierarchies of both companies.
You will be given the descriptions of all mergers. Depending on how they are
performed (which of the two presidents involved becomes the president of
the new company), the hierarchy can of the final company can take different
shapes. We want the hierarchy of the final company to be as shallow as
possible. The task is to find the smallest possible number of levels in the
final hierarchy.
There is also a limit D on the number of direct reports any employee can
have. Because of this limit, there may be only one way to accomplish a
certain merger, or it might even be impossible. However, there will always
be some way to accomplish all the mergers.
Input
The first line contains the number of test cases T.
Each test case starts with a blank line. The next line contains two integers
, N and D.
Each of the following N-1 lines describes a single merger, with two integers
between 1 and N. These are the employees whose companies are merging. The
two employees will never already be part of the same company.
The mergers must be performed in the order in which they are given.
Constraints
5 ≤ T ≤ 20
2 ≤ N ≤ 30000
1 ≤ D ≤ 5000
The input test cases will be such that it is possible to accomplish all
mergers.
Output
For each of the test cases numbered in order from 1 to T, output "Case #i: "
followed by a single integer, the smallest number of levels in the final
hierarchy.
Examples
In the first example, we have N=3 and D=2. The first merger happens between
the companies of employees 1 and 2. In the resulting company we can have
employee 1 as the president with 2 as his report, or vice versa. Next this
company merges with the company of employee 3. If we have employee 3 become
the president, the hierarchy will be a chain 3-1-2 or 3-2-1. If 1 or 2
become the president, that president will have the other two employees as
direct reports. This last hierarchy has two levels.
Example inputExample output
5
3 2
1 2
1 3
3 1
1 2
1 3
4 2
4 2
2 1
3 2
5 2
5 2
4 5
2 1
3 1
6 3
6 1
4 2
1 4
5 6
3 6
Case #1: 2
Case #2: 3
Case #3: 3
Case #4: 3
Case #5: 4
【在 l*****a 的大作中提到】
: share 一下题目，大家讨论一下吧
p*2
17 楼
我觉得上边这道还算是有思路的。不过我们几个人都做错了。
i*r
18 楼
并查集
l*c
19 楼
Similar google interview questions
are
different
【在 p*****2 的大作中提到】
: 我觉得上边这道还算是有思路的。不过我们几个人都做错了。
are
different
【在 p*****2 的大作中提到】
: 我觉得上边这道还算是有思路的。不过我们几个人都做错了。
a*m
20 楼
牛！
【在 B******5 的大作中提到】
: 这么快。。。
: 我一个好友进前100了。。。
【在 B******5 的大作中提到】
: 这么快。。。
: 我一个好友进前100了。。。
h*s
21 楼
UnionFind + DP
are
different
【在 p*****2 的大作中提到】
: 我觉得上边这道还算是有思路的。不过我们几个人都做错了。
are
different
【在 p*****2 的大作中提到】
: 我觉得上边这道还算是有思路的。不过我们几个人都做错了。
相关阅读