NO ACM NO LIFE

View as PDF

Submit solution

All submissions

Best submissions

Points: 30 (partial)

Time limit: 1.4s

Java 8 2.75s

Memory limit: 128M

Problem types

There is an old country and the king fell in love with a devil. The devil always asks the king to do some crazy things. Although the king used to be wise and beloved by his people, now he is just like a boy in love and can't refuse any request from the devil. Also, this devil looks like a very cute loli.

If you solved the last problem, you will see that the devil can't figure out who is z*p because there are too many people. So anyway, she decided to let it go.

The devil thinks she is the cutest loli in the world, but there are some people in the kingdom who don't think so. And they think WJMZBMR is the cutest loli.

It seems a war is approaching, but in this kingdom, due to old traditions, every conflict is solved by an algorithm contest!

One day, WJMZBMR is hanging out with her friend sevenkplus on the street. And she noticed that there is a group of people playing an algorithm contest to decide who is the cutest loli in the kingdom. One problem attracts her interest:

Given a tree with $n$ ~n~ vertices, we randomly choose $k$ ~k~ vertices of it. Then we can induce a subtree which is the smallest connected subtree of the original tree containing those $k$ ~k~ vertices.

Each vertex has a label, which is an integer. For an induced subtree, we look at its diameter $a - b$ ~a - b~, (if there are many diameters, pick the one with the smallest $a$ ~a~, and if there is still more than one, then the smallest $b$ ~b~). Finally, output how many distinct labels are on the diameter.

What is the expected value we output?

Of course, WJMZBMR is merely a cute loli and doesn't know much about the algorithm contest, but since you are a member of the Princess's Knights, you should solve it for your princess. Can you do it?

Input Specification

The first line contains an integer $T$ ~T~, denoting the number of the test cases.
For each test case, the first line contains two integers $n$ ~n~, $k$ ~k~.
The next $n-1$ ~n-1~ lines each contain two integers $a$ ~a~ and $b$ ~b~, meaning there is an edge between $a$ ~a~ and $b$ ~b~.
The next line contains $n$ ~n~ integers separated by a single space, denoting each vertex's label from vertex $1$ ~1~ to $n$ ~n~.

Constraints

$1 \le T \le 20$ ~1 \le T \le 20~
$2 \le k \le n \le 300$ ~2 \le k \le n \le 300~
$1 \le label \le 10^9$ ~1 \le label \le 10^9~

Output Specification

For each case, output the result.
Absolute or relative error less than $10^{-6}$ ~10^{-6}~ will be accepted.

Sample Input

1
20 8
2 1
3 1
4 1
5 4
6 3
7 2
8 4
9 5
10 5
11 10
12 11
13 10
14 11
15 12
16 12
17 14
18 13
19 18
20 17
5 6 2 1 2 4 7 3 1 3 5 4 1 7 2 6 1 2 1 5

Sample Output

5.7866158609

Original Problem Author: WJMZBMR; Problem Resource: HDU 4900

Comments

-16

isaacpino99 commented on April 25, 2018, 4:39 p.m.

this is fucked up. cute lolis? are dmoj's admins depraved older men?

This comment is hidden due to too much negative feedback. Show it anyway.

15

Xyene commented on April 26, 2018, 7:32 a.m. ← edit 2 →

You seem to be under the impression that every problem on the judge is written by an admin, or is even original to DMOJ. This problem is from HDU.

1

kobortor commented on March 16, 2016, 3:47 a.m.

My solution gets AC here but gets WA on the HDU judge. Has anyone else tried submitting there?

1

FatalEagle commented on March 16, 2016, 5:41 a.m.

It's not exact same problem. We have slightly different constraints. Plus I generated data randomly, but without looking at your submission i highly suspect its the (IMO really dumb) corner case.