Edgy Trees | Editorial by mota1997

This problem needs a bit of inclusion-exclusion principle. Instead of trying to find out the number of beautiful path, lets try finding the number of paths which are not beautiful.
A path will be not be a beautiful path if they are red edges. Now, let us find the number of nodes that are connected by only red edges ( if a node is connected to both red and a black edge we will still select that node as it is also going to contribute in our answer. ) So, how to do that efficiently ? Hopefully it turns out that in order to find out the nodes connected by red edges, we have to find out the connected components of the tree connected only by red edges. This can be done in O(n) time. Now, comes the part of combinatorics. We need to count all the possible ways to place these nodes in exactly k places. This is nothing but ` pow(p,k)` .
And why so? Say you have places and you have to place p elements and you have infinite supply for each elements of p which implies that repetition is allowed, then we will have pow(p,k) ways to place p elements.
What remains is to calculate the answer to the problem. It is pow(n,k) - sum(pow(p,k)) Refer to my [solution](https://codeforces.com/contest/1139/submission/51642015) for implementational details.

Happy Coding :)

Edgy Trees | Editorial by mota1997

Download submission

All caught up!

View submission

Is your resume even shortlisted?