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 is looking 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 think she is the cutest loli in the world, but there is some people in the kingdom don't think so. And they think WJMZBMR is the most cutest loli.
It seems a war is approaching, but in this kingdom, due to the old tradition, every conflict is solved by Algorithm contest!
One day, WJMZBMR is hanging out with her friend s***kplus on the street. And she noticed that there is a group of people playing algorithm contest to decide who is the cutest loli in the kingdom. One problem attracts her interest:
Given a tree with n vertices, we randomly choose k vertices of it. Then we can induced a subtree which is the smallest connected subtree of the original tree containing those k vertices.
Each vertex has a label(an integer), for a subtree we induced, we look at its diameter a-b,(if there are many diameters, pick the one with the smallest a, and then the smallest b). And output how many distinct label are on the diameter.
What is the expected value we output?
Of course, WJMZBMR is merely a cute loli and don't know much about the algorithm contest, but since you are a member of Princess's Knight, you should solve it for your princess, can you do it?