it seems that using only DP formula F(N,K) = (F(N-1, K) + K)%n is not enough...is there any critical observation?

I'm glad to see you trying to solve this problem. This problem can be solved in several ways, as the time limit is very loose. Here is the fastest way I could ever come up with.

Let the maximum depth be $$$H$$$. The number of nodes in the trie is $$$\mathcal{O}((n + m) H)$$$, but the number of useful nodes is only $$$\mathcal{O}(n + m)$$$. You can easily rebuild the tree for useful nodes.

Let's design a matching DP on the tree. In the DP state, we can either memorize the information in a subtree or the information on the path between the current node and the root. It's obvious that the latter is better, as $$$H$$$ is quite small.

So what's the state? Well, there are $$$5$$$ ways of matching: ($$$A \to B$$$ means that $$$A$$$ is an ancestor of $$$B$$$)

• main account $$$\to$$$ sockpuppet;
• sockpuppet $$$\to$$$ main account;
• main account $$$\to$$$ sockpuppet 1, main account $$$\to$$$ sockpuppet 2;
• sockpuppet 1 $$$\to$$$ main account $$$\to$$$ sockpuppet 2;
• sockpuppet 1 $$$\to$$$ sockpuppet 2 $$$\to$$$ main account.

You may design a DP like $$$dp(u, c_1, c_2, c_3)$$$ where

• the current node is $$$u$$$;
• there are $$$c_1$$$ unmatched sockpuppets as ancestors of $$$u$$$, which must be matched with some nodes in the subtree of $$$u$$$;
• there are $$$c_2$$$ unmatched main account as ancestors of $$$u$$$, which must be matched with some nodes in the subtree of $$$u$$$;
• there are $$$c_3$$$ unmatched pairs of sockpuppets (sockpuppet 1 $$$\to$$$ sockpuppet 2) as ancestors of $$$u$$$, which must be matched with some nodes in the subtree of $$$u$$$.

The above DP may work in $$$\mathcal{O}((n + m) H^5)$$$, because of the transition $$$dp(u, p_1 + q_1, p_2 + q_2, p_3 + q_3) \gets dp(v_1, p_1, p_2, p_3) dp(v_2, q_1, q_2, q_3)$$$ for each node $$$u$$$ and its children nodes $$$u_1$$$, $$$u_2$$$. However, as the modulo number is a big prime number, it is not difficult to squeeze out $$$c_3$$$, and then the time complexity will become $$$\mathcal{O}((n + m) H^3)$$$. (The complexity analysis is left to readers :P)

Actually, the constant factor yielded in each solution is very small (e.g. $$$1 / 24$$$ or $$$1 / 120$$$), so it's not difficult to pass.

Hint: For each position, there is at most one candidate with a high probability (greater than 0.5). If a matching occurs with a low probability (less than 1e-9), you can regard the probability as 0.

Write down the generating function and you will find the solution.

In wanna-fly camp, Claris taught some tricks about this problem. Maybe you can solve this problem now if the problem becomes 01 backpack. Don't worry. You can solve it by understanding some of the knowledge about generating functions. A backpack for an item can be seen as $$$\sum_{i=0}^{a} x ^{bi} = \frac{1 - x ^{(a+1)b}}{1-x^b} $$$. First use (a+1)b to make a 01 backpack with a negative coefficient, and then divide by a x^b 01 backpack. Because $$$\sum_{i=0}^{\infty} x ^{bi} = \frac{1}{1-x^b} $$$, you can solve this division problem by doing a full backpack with a positive coefficient on x^b. About the deleted backpack，you can also solve by the way. $$$(1-x^b)*\sum_{i=0}^{\infty} x ^{i*(a+1)b} = \frac{1-x^b}{1 - x ^{(a+1)b}} $$$.The remaining questions (such as prefixes and the like) have already been mentioned by Claris. My English is poor, hope you can understand and then solve this interesting problem.

It seemed to be a notorious coincidence: 1019E - Raining season (if we restrain all $$$a_i = 1$$$, then we get 101955D - Diameter of a Tree)

Though the tutorial for 1019E illustrated a solution running in $$$O(n \log^2 n + m)$$$, you can carefully modify that solution and make it run in $$$O(n \log n + m \log m)$$$ on 101955D.

The author's solution to 101955D is a bit complicated over data structure rather than geometry. To make it short, add some virtual vertices so that the degree of each vertex is at most 3, and then apply centroid decomposition and solve queries offline.

K — Let the Flames Begin