As you guys may notice, there is a big gap between Div1C and Div1D. We apologize for our inaccurate measure of the difficulty of Div1 D and Div1F1. In fact, many testers solved this problem during their VP. I think it's because CNOIers trained such kind of problems more, I mean combinatorics and counting. As you can see this round contains a lot of math things, Div1 DEF really sound like math problems. Previously, we think problems should more like this (math, finding lemma, observation) rather than graph+data structures+strings. This is because we want to do something new. In peoples mind, CN rounds usually means data structures+(graph/string/FFT) which is not interesting at all.

I discovered that many participants asked about Div2B. Honestly, I was confused as well when I was testing the round. I told this to the author but later we decide to keep that discription. This ended up in a big trouble which we haven't thought about before.

There are also some problems about the test data. System test is not strong enough and some strange code passed the final test. We notice this by checking 3 suspicious challenges. It turns out that the reason it that only the author of each problem made the data of his problem.

We will design more contests in the future. And we will try to avoid these problems. If you have anything that you want to say to us or any uncomfortable experience you encountered during the contest, just let us know.

The first step is how to deal with (f(x))^k.Here we can use Stirling Number of the second kind. Let's define S(i, j) the number of ways to put i different elements into j sets and there are no empty set.Note that the all j sets are the same.For example S(3, 2) = 3.The three ways are {{1}, {2, 3}}, {{1, 2}, {3}}, {{1, 3}, {2}}.So we have:

How to proof it?a^b is the number of ways to put b different elements into a different sets and empty sets are allowed.The other side of the equation means we select i sets from a sets and arrange them in i! different orders and put b different elements in it. So the fomula in the statement becomes:

Which equals to:

For we can use the following O(k²) DP to calculate all S(k, i).

Which means we consider the ith element.It can form a set by its own.Or you can insert it into one of those j sets.

For we use tree DP. Let's define g_ij the number of sets X plus the number of some tricky situation(I'll show you what it is later) when we select j edges in the subtree of node i.In addition,there should exist a node for every selected edge (u, v)(depth_u < depth_v) that w is in the subtree of v.The initial value is:

Means we can choose node i or not. When we add an child ch of i into our DP states we go through every possible l and we select l edges in the subtree of ch or we select l - 1 edges in the subtree of ch and select edge (i, ch).So we have:

Where g' is the previous state without add informations of ch.Note that in order to hold "there should exist a node for every selected edge (u, v)(depth_u < depth_v) that w is in the subtree of v" we have to minus 1 invalid state which is "select edge (u, v) but select no node in the subtree of ch". And for answer,we have to know what are those tricky situation.For example,we only select nodes from one subtree of i and some of the edges cannot be selected according to the defination of f because none of their ancestors is selected.So we have to go through all the children of i and minus them.Let's define h_ij be the number of sets X when we select j edges in the subtree of node i.So we have:

And now we finally have:

The total complexity is O(nk + k²). Why is the complexity O(nk + k²)?Calculating Stirling numbers is O(k²).And for DP on tree,when we merge two subtrees A and B with size size_A and size_B,the complexity is O(min(size_A, k), min(size_B, k)) which also means to merge the right min(size_a, k) edges from A and the left min(size_b, k) edges from B.So if we put all edges in a line and two edges all be merged only if their distance  < 2k.So the complexity of DP is O(nk).

My code:https://codeforces.me/contest/1097/submission/48058882